{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Visited Nodes in a Directed Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #memoization #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #记忆化搜索 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countVisitedNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有向图访问计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一个有向图，其中包含 <code>n</code> 个节点，节点编号从 <code>0</code> 到 <code>n - 1</code> 。此外，该图还包含了 <code>n</code> 条有向边。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的数组 <code>edges</code> ，其中 <code>edges[i]</code> 表示存在一条从节点 <code>i</code> 到节点 <code>edges[i]</code> 的边。</p>\n",
    "\n",
    "<p>想象在图上发生以下过程：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你从节点 <code>x</code> 开始，通过边访问其他节点，直到你在<strong> 此过程 </strong>中再次访问到之前已经访问过的节点。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回数组 <code>answer</code> 作为答案，其中 <code>answer[i]</code> 表示如果从节点 <code>i</code> 开始执行该过程，你可以访问到的不同节点数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/08/31/graaphdrawio-1.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>edges = [1,2,0,0]\n",
    "<strong>输出：</strong>[3,3,3,4]\n",
    "<strong>解释：</strong>从每个节点开始执行该过程，记录如下：\n",
    "- 从节点 0 开始，访问节点 0 -&gt; 1 -&gt; 2 -&gt; 0 。访问的不同节点数是 3 。\n",
    "- 从节点 1 开始，访问节点 1 -&gt; 2 -&gt; 0 -&gt; 1 。访问的不同节点数是 3 。\n",
    "- 从节点 2 开始，访问节点 2 -&gt; 0 -&gt; 1 -&gt; 2 。访问的不同节点数是 3 。\n",
    "- 从节点 3 开始，访问节点 3 -&gt; 0 -&gt; 1 -&gt; 2 -&gt; 0 。访问的不同节点数是 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/08/31/graaph2drawio.png\" style=\"width: 191px; height: 251px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>edges = [1,2,3,4,0]\n",
    "<strong>输出：</strong>[5,5,5,5,5]\n",
    "<strong>解释：</strong>无论从哪个节点开始，在这个过程中，都可以访问到图中的每一个节点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == edges.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= edges[i] &lt;= n - 1</code></li>\n",
    "\t<li><code>edges[i] != i</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-visited-nodes-in-a-directed-graph](https://leetcode.cn/problems/count-visited-nodes-in-a-directed-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-visited-nodes-in-a-directed-graph](https://leetcode.cn/problems/count-visited-nodes-in-a-directed-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,0,0]', '[1,2,3,4,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        N = len(edges)\n",
    "        dist = [0] * N\n",
    "        for i in edges:\n",
    "            dist[i] += 1                \n",
    "        def bfs(starts, dist: List[int]):\n",
    "            q = deque(starts)\n",
    "            while q:\n",
    "                i = q.popleft()\n",
    "                nxt = edges[i]\n",
    "                dist[nxt] -= 1\n",
    "                if dist[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "        starts = []\n",
    "        for i, d in enumerate(dist):\n",
    "            if d == 0:\n",
    "                starts.append(i)\n",
    "        bfs(starts, dist)\n",
    "        def circle(i: int, ans: List[int]):\n",
    "            j = i\n",
    "            cnt = 1\n",
    "            while edges[j] != i:\n",
    "                cnt += 1\n",
    "                j = edges[j]\n",
    "            j = i\n",
    "            while edges[j] != i:\n",
    "                ans[j] = cnt\n",
    "                j = edges[j]\n",
    "            ans[j] = cnt\n",
    "        \n",
    "        ans = [0] * N\n",
    "        for i, d in enumerate(dist):\n",
    "            if d != 0 and ans[i] == 0:\n",
    "                circle(i, ans)\n",
    "        for i in starts:\n",
    "            stack = []\n",
    "            while dist[i] == 0:\n",
    "                stack.append(i)\n",
    "                i = edges[i]\n",
    "            L, loop = len(stack), ans[i]\n",
    "            for i in range(1, L+1):\n",
    "                ans[stack[L-i]] = i + loop\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(edges)\n",
    "        \n",
    "        cnt = [0 for e in edges]\n",
    "        res = [0 for e in edges]\n",
    "        la = 1\n",
    "        for i in range(n):\n",
    "            if cnt[i] == 0:\n",
    "                cnt[i] = la\n",
    "                la += 1\n",
    "                \n",
    "                now = edges[i]\n",
    "                \n",
    "                while cnt[now] == 0:\n",
    "                    cnt[now] = la\n",
    "                    la += 1\n",
    "                    now = edges[now]\n",
    "                    \n",
    "                if res[now] == 0:\n",
    "                \n",
    "                    cur = i\n",
    "\n",
    "                    while cur != now:\n",
    "                        res[cur] = la - cnt[cur]\n",
    "                        cur = edges[cur]\n",
    "\n",
    "                    cir = la - cnt[cur]\n",
    "                    res[cur] = cir\n",
    "\n",
    "                    cur = edges[cur]\n",
    "                    while cur != now:\n",
    "                        res[cur] = cir\n",
    "                        cur = edges[cur]\n",
    "                else:\n",
    "                    rem = la - cnt[i]\n",
    "                    \n",
    "                    cur = i\n",
    "                    while cur != now:\n",
    "                        res[cur] = rem + res[now]\n",
    "                        rem -= 1\n",
    "                        cur = edges[cur]\n",
    "                #print(cnt,res)\n",
    "        return res\n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        adj = list(edges)\n",
    "        n = len(adj)\n",
    "        result = [0] * n\n",
    "        time = [0] * n\n",
    "        clock = 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if time[i] > 0:\n",
    "                continue\n",
    "            \n",
    "            x = i\n",
    "            start_time = clock\n",
    "            while time[x] == 0:\n",
    "                time[x] = clock\n",
    "                clock += 1\n",
    "                x = adj[x]\n",
    "            \n",
    "            count = clock - start_time + result[x]\n",
    "            k = i\n",
    "            while k != x:\n",
    "                result[k] = count\n",
    "                count -= 1\n",
    "                k = adj[k]\n",
    "            \n",
    "            k = x\n",
    "            while result[k] == 0:\n",
    "                result[k] = count\n",
    "                k = adj[k]   \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            if ans[i] != 0:\n",
    "                continue\n",
    "            node2idx = {}\n",
    "            cur = i\n",
    "            idx = 0\n",
    "            while cur not in node2idx and ans[cur] == 0:\n",
    "                node2idx[cur] = idx\n",
    "                cur = edges[cur]\n",
    "                idx += 1\n",
    "            if ans[cur] == 0: # find a new ring\n",
    "                ringSize = idx - node2idx[cur]\n",
    "                ans[cur] = ringSize\n",
    "\n",
    "                # ring part\n",
    "                j = edges[cur]\n",
    "                while j != cur:\n",
    "                    ans[j] = ringSize\n",
    "                    j = edges[j]\n",
    "\n",
    "                # branch part\n",
    "                j = i\n",
    "                while j != cur:\n",
    "                    ans[j] = idx - node2idx[j]\n",
    "                    j = edges[j]                \n",
    "\n",
    "            else: # meet previous answer -> only branch here\n",
    "                j = i\n",
    "                while j != cur:\n",
    "                    ans[j] = idx - node2idx[j] + ans[cur]\n",
    "                    j = edges[j]  \n",
    "        return ans              \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            if ans[i]:\n",
    "                continue\n",
    "            step = 0\n",
    "            cur = i\n",
    "            records = {}\n",
    "            while True:\n",
    "                if cur in records:\n",
    "                    start = records[cur]\n",
    "                    length = step - start\n",
    "                    for j, k in records.items():\n",
    "                        ans[j] = length if k >= start else start - k + length\n",
    "                    break\n",
    "                if ans[cur]:\n",
    "                    for j, k in records.items():\n",
    "                        ans[j] = ans[cur] + step - k\n",
    "                    break\n",
    "                records[cur] = step\n",
    "                step += 1\n",
    "                cur = edges[cur]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        \"\"\"https://leetcode.com/problems/count-visited-nodes-in-a-directed-graph/solutions/4112091/java-c-python-stack-solution-no-dfs-no-topo/\n",
    "        stack\"\"\"\n",
    "        n = len(edges)\n",
    "        res = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            seen = OrderedDict()\n",
    "            j = i\n",
    "            while (j not in seen) and (res[j] == 0):\n",
    "                seen[j] = len(seen)\n",
    "                j = edges[j]\n",
    "            if j in seen:\n",
    "                k = len(seen) - seen[j]\n",
    "                for _ in range(k):\n",
    "                    res[seen.popitem()[0]] = k\n",
    "            while seen:\n",
    "                j = seen.popitem()[0]\n",
    "                res[j] = res[edges[j]] + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        ret = [-1]*n\n",
    "        visit ={}\n",
    "        st=[]\n",
    "        def dfs(a):\n",
    "            sst =[]\n",
    "            sst.append(a)\n",
    "            while sst:\n",
    "                a = sst.pop()\n",
    "                if a not in visit:\n",
    "                    visit[a] = 1\n",
    "                    st.append(a)\n",
    "                    sst.append(edges[a])\n",
    "                else:\n",
    "                    if ret[a]==-1:\n",
    "                        cir =[]\n",
    "                        cnt = 0\n",
    "                        while st[-1]!=a:\n",
    "                            cir.append(st[-1])\n",
    "                            st.pop()\n",
    "                            cnt +=1\n",
    "                        cir.append(st[-1])\n",
    "                        st.pop()\n",
    "                        cnt +=1\n",
    "                        for a in cir:\n",
    "                            ret[a] = cnt\n",
    "                    while st:\n",
    "                        a = st.pop()\n",
    "                        ret[a] = ret[edges[a]] +1\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        # 相互独立的，带环的链表\n",
    "        # 环上就是环长\n",
    "        # 链上就是集合大小-第几个\n",
    "        n = len(edges) \n",
    "         \n",
    "        degree = [0]*n\n",
    "        for i,e in enumerate(edges): \n",
    "            degree[e]+=1\n",
    "        \n",
    "        ans = [0]*n \n",
    " \n",
    "        rings = set()\n",
    "        for i in range(n):\n",
    "            if ans[i] != 0:continue\n",
    "            path = []\n",
    "            ne = i\n",
    "            t = 0\n",
    "            hashmap = {i:t} \n",
    "            circle = 0\n",
    "            path.append(i)\n",
    "            while True: \n",
    "                ne = edges[ne]\n",
    "                if ans[ne]>0:\n",
    "                    incr = ans[ne]\n",
    "                    for p in path[::-1]:\n",
    "                        incr += 1\n",
    "                        ans[p] = incr\n",
    "                    break\n",
    "\n",
    "                if ne not in hashmap:\n",
    "                    t += 1\n",
    "                    hashmap[ne] = t\n",
    "                    path.append(ne)\n",
    "                else:\n",
    "                    circle = t + 1- hashmap[ne] \n",
    "                    for p in path[-circle:]: \n",
    "                        ans[p] = circle\n",
    "                        rings.add(p)\n",
    "                    incr = circle\n",
    "                    for p in path[:-circle][::-1]:\n",
    "                        incr += 1\n",
    "                        ans[p] = incr\n",
    "                    break\n",
    "                    \n",
    "          \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        g = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for a, b in enumerate(edges):\n",
    "            g[b].append(a)\n",
    "            deg[b] += 1\n",
    "        q = deque([i for i in range(n) if not deg[i]])\n",
    "        \n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            j = edges[t]\n",
    "            deg[j] -= 1\n",
    "            if not deg[j]:\n",
    "                q.append(j)\n",
    "        ans = [-1] * n\n",
    "        def dfs(u, d):\n",
    "            ans[u] = d\n",
    "            for j in g[u]:\n",
    "                if not deg[j]:\n",
    "                    dfs(j, d + 1)\n",
    "        for i in range(n):\n",
    "            if deg[i] > 0 and ans[i] == -1:\n",
    "                loop = [i]\n",
    "                y = edges[i]\n",
    "                while y != i:\n",
    "                    loop.append(y)\n",
    "                    y = edges[y]\n",
    "                d = len(loop)\n",
    "                for x in loop:\n",
    "                    dfs(x, d)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n=len(edges)\n",
    "        rg=[[] for _ in edges]\n",
    "        deg=[0]*n\n",
    "        ans=[1]*n\n",
    "        for i,e in enumerate(edges):\n",
    "            rg[e].append(i)\n",
    "            deg[e]+=1\n",
    "        q=deque(i for i in range(n) if deg[i]==0)\n",
    "        def rdfs(x,depth):\n",
    "            ans[x]=depth\n",
    "            for son in rg[x]:\n",
    "                if deg[son]==0:\n",
    "                    rdfs(son,depth+1)\n",
    "        while q:\n",
    "            x=q.popleft()\n",
    "            y=edges[x]\n",
    "            deg[y]-=1\n",
    "            if deg[y]==0:\n",
    "                q.append(y)\n",
    "        for i in range(n):\n",
    "            if deg[i]<=0: continue\n",
    "            now=i\n",
    "            ring=[i]\n",
    "            deg[i]=-1\n",
    "            i=edges[i]\n",
    "            loop_len=1\n",
    "            while now!=i:\n",
    "                deg[i]=-1           \n",
    "                loop_len+=1\n",
    "                ring.append(i)\n",
    "                i=edges[i]\n",
    "            for r in ring:\n",
    "                rdfs(r,loop_len)\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        # 有向基环树,这个似乎可以用并查集玩?\n",
    "        # 并查集似乎更麻烦一些,主要问题在于没有办法确定环\n",
    "        # class findUnion:\n",
    "        #     def __init__(self,n):\n",
    "        #         self.f=[x for x in range(n)]\n",
    "        #     def find(self,u):\n",
    "        #         if self.f[u]=u:\n",
    "        #             return u \n",
    "        #         self.f[u]=self.find(self.f[u])\n",
    "        #         return self.f[u]\n",
    "        #     def setU(self,u,v):\n",
    "        #         u,v=min(u,v),max(u,v)\n",
    "        #         self.f[v]=self.find(u) #这两个放在\n",
    "        # un=findUnion(len(edges))\n",
    "        class circle:\n",
    "            def __init__(self):\n",
    "                self.baseCircle=set()\n",
    "                self.belt=dict()\n",
    "            def f(self,n):\n",
    "                if n in self.baseCircle:\n",
    "                    return len(self.baseCircle)\n",
    "                if n in self.belt:\n",
    "                    return self.belt[n]+len(self.baseCircle)\n",
    "                return -1\n",
    "        circles=[]\n",
    "        n=len(edges)\n",
    "        res=[-1]*n\n",
    "        visited=set()\n",
    "        for i in range(n):\n",
    "            if i in visited:\n",
    "                continue\n",
    "            now=begin=i\n",
    "            tmp=dict()\n",
    "            index=0\n",
    "            while now not in visited:\n",
    "                tmp[now]=index\n",
    "                visited.add(now)\n",
    "                index+=1\n",
    "                now=edges[now]\n",
    "            #print(now,' ')\n",
    "            if now in tmp:\n",
    "                #此时tmp[now]长度为外面的带的长度,\n",
    "                c=circle()\n",
    "                length=tmp[now]\n",
    "                now=begin\n",
    "                while length>0:\n",
    "                    c.belt[now]=length\n",
    "                    length-=1\n",
    "                    now=edges[now]\n",
    "                while now not in c.baseCircle:\n",
    "                    c.baseCircle.add(now)\n",
    "                    now=edges[now]\n",
    "                for u in tmp:\n",
    "                    res[u]=c.f(u)\n",
    "            else:\n",
    "                length=index\n",
    "                baseLength=res[now]\n",
    "                now=begin\n",
    "                while length>0:\n",
    "                    res[now]=baseLength+length\n",
    "                    now=edges[now]\n",
    "                    length-=1\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        g_r = [[] for _ in range(n)]\n",
    "        indegree = [0] * n\n",
    "        for fr, to in enumerate(edges):\n",
    "            g_r[to].append(fr)\n",
    "            indegree[to] += 1\n",
    "        \n",
    "        q = deque([i for i, d in enumerate(indegree) if d == 0])\n",
    "        vis = [False] * n\n",
    "        while q:\n",
    "            fr = q.popleft()\n",
    "            vis[fr] = True\n",
    "            to = edges[fr]\n",
    "            indegree[to] -= 1\n",
    "            if indegree[to] == 0:\n",
    "                q.append(to)\n",
    "        \n",
    "        res = [0] * n\n",
    "        for nid in range(n):\n",
    "            if vis[nid]:\n",
    "                continue\n",
    "            \n",
    "            loop = set([nid])\n",
    "            cur = edges[nid]\n",
    "            while cur != nid:\n",
    "                loop.add(cur)\n",
    "                cur = edges[cur]\n",
    "\n",
    "            res[nid] = len(loop)\n",
    "            vis[nid] = True\n",
    "            cur = edges[nid]\n",
    "            while cur != nid:\n",
    "                res[cur] = len(loop)\n",
    "                vis[cur] = True\n",
    "                cur = edges[cur]\n",
    "            \n",
    "            dq = deque([])\n",
    "            for lid in loop:\n",
    "                dq.extend([(i, 1) for i in g_r[lid] if i not in loop])\n",
    "            \n",
    "            while dq:\n",
    "                lid, dis = dq.popleft()\n",
    "                res[lid] = len(loop) + dis\n",
    "                for to in g_r[lid]:\n",
    "                    dq.append((to, dis + 1))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        self.n = len(edges)\n",
    "        self.father = [[] for _ in range(self.n)]\n",
    "        self.answer = [-1] * self.n\n",
    "        for fa, child in enumerate(edges):\n",
    "            self.father[child].append(fa)\n",
    "        self.visited = [False] * self.n\n",
    "        for index, state in enumerate(self.visited):\n",
    "            if not state:\n",
    "                self.solve_each_part(index, edges)\n",
    "\n",
    "        return self.answer\n",
    "\n",
    "    def solve_each_part(self, pointer, edges):\n",
    "        index = pointer\n",
    "        temp = []\n",
    "        memory ={}\n",
    "        while not self.visited[index]:\n",
    "            self.visited[index] = True\n",
    "            temp.append(index)\n",
    "            memory[index] = len(temp) - 1\n",
    "            index = edges[index]\n",
    "        circle = temp[memory[index]:]\n",
    "        q = deque(circle)\n",
    "        length = len(q)\n",
    "        for each in q:\n",
    "            self.answer[each] = length\n",
    "        while q:\n",
    "            top = q.popleft()\n",
    "            for fa in self.father[top]:\n",
    "                if self.answer[fa] > 0:\n",
    "                    continue\n",
    "                self.visited[fa] = True\n",
    "                self.answer[fa] = self.answer[top] + 1\n",
    "                q.append(fa)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        in_dgr = [0] * n  #入度数组\n",
    "        tree = [[] for _ in range(n)]   #反向建树\n",
    "        vis = [False] * n\n",
    "        res = [0] * n\n",
    "\n",
    "        for u, v in enumerate(edges):\n",
    "            in_dgr[v] += 1\n",
    "            tree[v].append(u)\n",
    "\n",
    "        # 深度优先搜索树枝\n",
    "        def dfs(u: int, depth: int):\n",
    "            if vis[u]: \n",
    "                return \n",
    "            vis[u] = True\n",
    "            res[u] = depth\n",
    "            for v in tree[u]:\n",
    "                dfs(v, depth + 1)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if vis[i]:\n",
    "                continue\n",
    "            cyc_len, dnf, clock, p = 0, {}, 1, i\n",
    "            # Tarjan + 时间戳思想记录每个景区访问的时间\n",
    "            while True:\n",
    "                if dnf.get(p, 0) > 0:\n",
    "                    cyc_len = clock - dnf[p]\n",
    "                    break\n",
    "                dnf[p] = clock\n",
    "                p = edges[p]\n",
    "                clock += 1\n",
    "\n",
    "            brnch = []\n",
    "            while vis[p] != True:\n",
    "                res[p] = cyc_len \n",
    "                vis[p] = True\n",
    "                if in_dgr[p] > 1:\n",
    "                    brnch.append(p)\n",
    "                p = edges[p]\n",
    "\n",
    "            \n",
    "            for u in brnch:\n",
    "                for v in tree[u]:\n",
    "                    dfs(v, cyc_len + 1)\n",
    "\n",
    "        # print(tree, vis, in_dgr)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n=len(edges)\n",
    "        faedges=[[-1] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if len(faedges[edges[i]])==1 and faedges[edges[i]][0]==-1:\n",
    "                faedges[edges[i]]=[i]\n",
    "            else:\n",
    "                faedges[edges[i]].append(i)\n",
    "        # print(faedges)\n",
    "\n",
    "        res=[-1]*n\n",
    "        def dfs(x):\n",
    "            # print(x)\n",
    "            if (len(faedges[x])==1 and faedges[x][0]==-1):\n",
    "                return\n",
    "            for fa in faedges[x]:\n",
    "                if res[fa]!=-1 : continue\n",
    "                res[fa]=res[edges[fa]]+1\n",
    "                visited[fa]=True\n",
    "                dfs(fa)\n",
    "\n",
    "        def visit(x):\n",
    "            s=set()\n",
    "            for i in range(n+1):\n",
    "                if visited[edges[x]]:\n",
    "                    while True:\n",
    "                        res[x]=res[edges[x]]+1\n",
    "                        x=faedges[x][0]\n",
    "                        visited[x]=True\n",
    "                        if x==-1: break\n",
    "                    return\n",
    "                else:\n",
    "                    if x in s:\n",
    "                        break\n",
    "                    else:\n",
    "                        s.add(x)\n",
    "                        x=edges[x]\n",
    "            c=set()\n",
    "            for i in range(n+1):\n",
    "                if x in c:\n",
    "                    break\n",
    "                else:\n",
    "                    c.add(x)\n",
    "                    x=edges[x]\n",
    "            for i in c:\n",
    "                res[i]=len(c)\n",
    "                visited[i]=True\n",
    "\n",
    "            # print(c,visited,x,faedges[x])\n",
    "            for x in c:\n",
    "                if len(faedges[x])>1:\n",
    "                    dfs(x)\n",
    "            return\n",
    "\n",
    "        visited=[False]*n\n",
    "        for start in range(n):\n",
    "            if visited[start]: continue\n",
    "            # print(visited, start)\n",
    "            visit(start)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        g = defaultdict(list)\n",
    "        cnt = [0] * n\n",
    "        for i, v in enumerate(edges):\n",
    "            g[v].append(i)\n",
    "            cnt[v] += 1\n",
    "\n",
    "        def circle(root: int, pre: int):\n",
    "            if root not in vis:\n",
    "                vis.add(root)\n",
    "                nodes = [root]\n",
    "                cur = edges[root]\n",
    "                circleSize = 1\n",
    "                while cur != root:\n",
    "                    vis.add(cur)\n",
    "                    nodes.append(cur)\n",
    "                    cur = edges[cur]\n",
    "                    circleSize += 1\n",
    "                for node in nodes:\n",
    "                    ans[node] = circleSize\n",
    "            else:\n",
    "                circleSize = ans[root]\n",
    "\n",
    "            if pre != None:\n",
    "                depth = 1\n",
    "                q = [pre]\n",
    "                while q:\n",
    "                    nex = []\n",
    "                    for node in q:\n",
    "                        ans[node] = circleSize + depth\n",
    "                        if node in g:\n",
    "                            nex.extend(g[node])\n",
    "                    q = nex\n",
    "                    depth += 1\n",
    "\n",
    "        ans = [0] * n\n",
    "        vis = set()\n",
    "        q = deque([x for x, v in enumerate(cnt) if not v])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            cnt[edges[node]] -= 1\n",
    "            if not cnt[edges[node]]:\n",
    "                q.append(edges[node])\n",
    "        q = [x for x, v in enumerate(cnt) if v]\n",
    "        for node in q:\n",
    "            if len(g[node]) > 1:\n",
    "                for pre in g[node]:\n",
    "                    if not cnt[pre]:\n",
    "                        circle(node, pre)\n",
    "            else:\n",
    "                circle(node, None)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        indeg = [0] * n\n",
    "        r_g = defaultdict(list)\n",
    "\n",
    "        for node , nxt in enumerate(edges):\n",
    "            indeg[nxt] += 1\n",
    "            r_g[nxt].append(node)\n",
    "\n",
    "        queue = deque([node for node , v in enumerate(indeg) if v == 0])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            nxt = edges[node]\n",
    "            indeg[nxt] -= 1\n",
    "            if indeg[nxt] == 0:\n",
    "                queue.append(nxt)\n",
    "\n",
    "        ans = [0] * n\n",
    "\n",
    "        def dfs(node,deep):\n",
    "            ans[node] = deep\n",
    "            for nxt in r_g[node]:\n",
    "                if indeg[nxt] == 0:\n",
    "                    dfs(nxt,deep+1)\n",
    "\n",
    "        queue = deque([node for node , v in enumerate(indeg) if v != 0])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if indeg[node] <= 0:continue\n",
    "            visited = set()\n",
    "            while node not in visited:\n",
    "                visited.add(node)\n",
    "                indeg[node] = -1\n",
    "                node = edges[node]\n",
    "            length = len(visited)\n",
    "            for node in visited:\n",
    "                dfs(node,length)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        # 径向基环树\n",
    "\n",
    "        n = len(edges)\n",
    "        ans = [1] * n\n",
    "\n",
    "        # 拓扑排序\n",
    "        # 记录入度\n",
    "        ig = [0] * n # 入度\n",
    "        for e in edges:\n",
    "            ig[e] += 1\n",
    "        \n",
    "        q = deque(i for i in range(n) if ig[i] == 0)\n",
    "        visited = [False] * n\n",
    "        while len(q):\n",
    "            u = q.popleft()\n",
    "            v = edges[u]\n",
    "            visited[u] = True\n",
    "            ig[v] -= 1\n",
    "            if ig[v] == 0:\n",
    "                q.append(v)\n",
    "        cycle = visited.copy()  # 记录是不是在 圆环上的点\n",
    "        va = visited.copy()     # 记录是不是已经登记过ans长度\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                # 开始记录这个环\n",
    "                visited[i] = True\n",
    "                k = edges[i]\n",
    "                l = 1\n",
    "                while not visited[k]:\n",
    "                    visited[k] = True\n",
    "                    k = edges[k]\n",
    "                    l += 1\n",
    "                \n",
    "                ans[i] = l\n",
    "                k = edges[i]\n",
    "                while k != i:\n",
    "                    ans[k] = l\n",
    "                    k = edges[k]\n",
    "        \n",
    "        # 把路径上的节点加上环的长度\n",
    "        def getLength(x):\n",
    "            if not cycle[x]:\n",
    "                return ans[x]\n",
    "            else:\n",
    "                va[x] = False\n",
    "                ans[x] = getLength(edges[x]) + 1\n",
    "                return ans[x]\n",
    "        \n",
    "        for i in range(n):\n",
    "            if va[i]:\n",
    "                getLength(i)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n=len(edges)\n",
    "        ind={i:0 for i in range(n)}\n",
    "        rev=collections.defaultdict(list)\n",
    "        vis=[0]*n\n",
    "        for i in range(n):\n",
    "            e=edges[i]\n",
    "            ind[e]+=1\n",
    "            rev[e].append(i)\n",
    "        stack=[]\n",
    "        for x in ind:\n",
    "            if ind[x]==0:\n",
    "                stack.append(x)\n",
    "        #print(ind)\n",
    "        while stack:\n",
    "            cur=stack.pop()\n",
    "            vis[cur]=-1            \n",
    "            nex=edges[cur]\n",
    "            ind[nex]-=1\n",
    "            if ind[nex]==0:\n",
    "                stack.append(nex)\n",
    "      #  print(vis)\n",
    "      #  print(ind)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if vis[i]==0:\n",
    "                tmp=[i]\n",
    "                while edges[tmp[-1]]!=i:\n",
    "                    tmp.append(edges[tmp[-1]])\n",
    "                for x in tmp:\n",
    "                    vis[x]=len(tmp)\n",
    "       # print(vis)\n",
    "        for i in range(n):\n",
    "            if ind[i]==0:\n",
    "                continue\n",
    "            stack=[i]\n",
    "            while stack:\n",
    "                cur=stack.pop()\n",
    "                for nex in rev[cur]:\n",
    "                    if vis[nex]==-1:\n",
    "                        vis[nex]=vis[cur]+1\n",
    "                        stack.append(nex)\n",
    "                \n",
    "                        \n",
    "       \n",
    "        return vis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        graph = collections.defaultdict(list)\n",
    "        r = collections.defaultdict(list)\n",
    "        ind = collections.Counter()\n",
    "        for a in range(n):\n",
    "            b = edges[a]\n",
    "            r[b].append(a)\n",
    "            ind[b] += 1 \n",
    "        queue = collections.deque([node for node in range(n) if node not in ind])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            nei = edges[cur]\n",
    "            ind[nei] -= 1 \n",
    "            if ind[nei] == 0:\n",
    "                queue.append(nei)\n",
    "        res = [0] * n \n",
    "        def get_depth(node, d):\n",
    "            res[node] = d \n",
    "            for nei in r[node]:\n",
    "                if ind[nei] == 0:\n",
    "                    get_depth(nei, d + 1)\n",
    "        for node in range(n):\n",
    "            if ind[node] <= 0:\n",
    "                continue \n",
    "            cycle = []\n",
    "            start = node \n",
    "            while True:\n",
    "                cycle.append(start)\n",
    "                start = edges[start]\n",
    "                if start == node:\n",
    "                    break \n",
    "            for c in cycle:\n",
    "                ind[c] = - 1\n",
    "                get_depth(c, len(cycle))\n",
    "        return res \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        N = len(edges)\n",
    "        ret = [0] * N\n",
    "\n",
    "        # 记录每个点的入点\n",
    "        l_in = [set() for _ in range(N)]\n",
    "\n",
    "        for i, out in enumerate(edges):\n",
    "            l_in[out].add(i)\n",
    "\n",
    "        # 所有出点的集合\n",
    "        s_out = set(edges)\n",
    "\n",
    "        while s_out:\n",
    "            l = [s_out.pop()]\n",
    "\n",
    "            while 1:\n",
    "                u = edges[l[-1]]\n",
    "                if u in s_out:\n",
    "                    l.append(u)\n",
    "                    s_out.remove(u)\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            # 保证l为环\n",
    "            del l[:l.index(u)]\n",
    "\n",
    "            n = len(l)\n",
    "            dp = [(u, l[i - 1], n) for i, u in enumerate(l)]\n",
    "\n",
    "            while dp:\n",
    "                u, p, n = dp.pop()\n",
    "                ret[u] = n\n",
    "\n",
    "                for v in l_in[u]:\n",
    "                    if v != p:\n",
    "                        s_out.discard(v)\n",
    "                        dp.append((v, -1, n + 1))\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        r_g = defaultdict(list)\n",
    "        indeg = defaultdict(int)\n",
    "\n",
    "        for u , v in enumerate(edges):\n",
    "            r_g[v].append(u)\n",
    "            indeg[v] += 1\n",
    "        \n",
    "        queue = deque([i for i in range(len(edges)) if indeg[i] == 0])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            nxt = edges[node]\n",
    "            indeg[nxt] -= 1\n",
    "            if indeg[nxt] == 0:\n",
    "                queue.append(nxt)\n",
    "\n",
    "        queue = deque([i for i in range(len(edges)) if indeg[i] != 0])\n",
    "\n",
    "        def dfs(node,deep):\n",
    "            ans[node] = deep\n",
    "            for nxt in r_g[node]:\n",
    "                if nxt not in q:\n",
    "                    dfs(nxt,deep+1)\n",
    "\n",
    "        ans = [0] * len(edges)\n",
    "\n",
    "        for node in queue:\n",
    "            if indeg[node] == 0:continue\n",
    "            x = node\n",
    "            q = set()\n",
    "            while True:\n",
    "                q.add(x)\n",
    "                x = edges[x]\n",
    "                indeg[x] -= 1\n",
    "                if x == node:break\n",
    "            \n",
    "            for x in q:\n",
    "                dfs(x,len(q))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        d = {}\n",
    "        for i in range(len(edges)):\n",
    "            l, x = [], i\n",
    "            while x not in d:\n",
    "                d[x] = None\n",
    "                l.append(x)\n",
    "                x = edges[x]\n",
    "            p = len(d) if x not in l else l.index(x)\n",
    "            for x in l[:p]: d[x] = [0, -1]\n",
    "            for x in l[p:]: d[x] = [1, len(l)-p]\n",
    "\n",
    "        @cache\n",
    "        def f(x): return d[x][1] if d[x][0]==1 else 1+f(edges[x])\n",
    "        \n",
    "        return [f(i) for i in range(len(d))]      \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        I = [0] * n\n",
    "        G = defaultdict(list)\n",
    "        for idx,i in enumerate(edges):\n",
    "            G[i].append(idx)\n",
    "            I[i] += 1\n",
    "        CI = [0] * (n+5)\n",
    "        Res = [0] * n\n",
    "        @cache\n",
    "        def dfs(cur):\n",
    "            if CI[cur]:return CI[cur]\n",
    "            nxt = edges[cur]\n",
    "            v = dfs(nxt) + 1\n",
    "            Res[cur] = v\n",
    "            return v\n",
    "        \n",
    "        q = []\n",
    "        for idx,i in enumerate(I):\n",
    "            heappush(q,(i,idx))\n",
    "        while q:\n",
    "            i,cur = heappop(q)\n",
    "            s = cur\n",
    "            if Res[cur]:continue\n",
    "            else:\n",
    "                flag = 1\n",
    "                S = set()\n",
    "                while cur not in S:\n",
    "                    if Res[cur]:flag = 0;break\n",
    "                    S.add(cur)\n",
    "                    cur = edges[cur]\n",
    "                if flag:\n",
    "                    cnt = 0\n",
    "                    S1 = set()\n",
    "                    while cur not in S1:\n",
    "                        S1.add(cur)\n",
    "                        cur = edges[cur]\n",
    "                        cnt += 1\n",
    "                    st = []\n",
    "                    for x in S1:\n",
    "                        CI[x] = cnt\n",
    "                        Res[x] = cnt\n",
    "                dfs(s)\n",
    "        return Res\n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        fan_child = defaultdict(list)\n",
    "        ru = defaultdict(int)\n",
    "        n = len(edges)\n",
    "        \n",
    "        for i in range(n):\n",
    "            ru[edges[i]] += 1\n",
    "            fan_child[edges[i]].append(i)\n",
    "            \n",
    "        all_zero = deque()\n",
    "        for i in range(n):\n",
    "            if ru[i] == 0:\n",
    "                all_zero.append(i)\n",
    "                \n",
    "        visited = set()\n",
    "                \n",
    "        last_node = 0\n",
    "        while all_zero:\n",
    "            cur = all_zero.popleft()\n",
    "            last_node = cur\n",
    "            visited.add(cur)\n",
    "            child = edges[cur]\n",
    "            ru[child] -= 1\n",
    "            if ru[child] == 0:\n",
    "                all_zero.append(child)\n",
    "                        \n",
    "        not_visited = []          \n",
    "        if len(visited) != n:\n",
    "            for i in range(n):\n",
    "                if i not in visited:\n",
    "                    not_visited.append(i)\n",
    "            huan_dict = dict()\n",
    "            v = set()\n",
    "            for node in not_visited:\n",
    "                if node in v:\n",
    "                    continue\n",
    "                huan = [node]\n",
    "                start = node\n",
    "                while True:\n",
    "                    v.add(node)\n",
    "                    child = edges[node]\n",
    "                    if child == start:\n",
    "                        break\n",
    "                    huan.append(child)\n",
    "                    node = child\n",
    "                huan_l = len(huan)\n",
    "                for node in huan:\n",
    "                    huan_dict[node] = huan_l\n",
    "        else:\n",
    "            not_visited = [last_node]\n",
    "            huan_dict[last_node] = 1\n",
    "            \n",
    "        res = [0] * n\n",
    "            \n",
    "        def dfs(node, visited, cur_count):\n",
    "            nonlocal res\n",
    "            nonlocal not_visited\n",
    "            visited.add(node)\n",
    "            res[node] = cur_count\n",
    "            for child in fan_child[node]:\n",
    "                if child in visited or child in not_visited:\n",
    "                    continue\n",
    "                dfs(child, visited, cur_count+1)\n",
    "                            \n",
    "        visited = set()\n",
    "        for not_v in not_visited:\n",
    "            dfs(not_v, visited, huan_dict[not_v])\n",
    "                    \n",
    "        return res\n",
    "                \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        d = [0] * n\n",
    "        res = [0] * n\n",
    "\n",
    "        for x, y in enumerate(edges):\n",
    "            d[y] += 1\n",
    "        \n",
    "        q = deque()\n",
    "        for i, x in enumerate(d):\n",
    "            if x == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            y = edges[x]\n",
    "            d[y] -= 1\n",
    "            if d[y] == 0:\n",
    "                q.append(y)\n",
    "\n",
    "        for i in range(n):\n",
    "            if d[i] <= 0:\n",
    "                continue\n",
    "            \n",
    "            x = i\n",
    "            ring = [x]\n",
    "            x = edges[x]\n",
    "            while x != i:\n",
    "                d[x] = -1\n",
    "                ring.append(x)\n",
    "                x = edges[x]\n",
    "\n",
    "            for x in ring:\n",
    "                res[x] = len(ring)\n",
    "\n",
    "        def dfs(x):\n",
    "            if res[x] != 0 or d[x] == -1:\n",
    "                return res[x]\n",
    "            res[x] = dfs(edges[x]) + 1\n",
    "            return res[x]\n",
    "        \n",
    "        for i in range(n):\n",
    "            if d[i] == 0:\n",
    "                dfs(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        fan_child = defaultdict(list)\n",
    "        \n",
    "        ru = defaultdict(int)\n",
    "        \n",
    "        n = len(edges)\n",
    "        \n",
    "        for i in range(n):\n",
    "            ru[edges[i]] += 1\n",
    "            fan_child[edges[i]].append(i)\n",
    "            \n",
    "        all_zero = deque()\n",
    "        for i in range(n):\n",
    "            if ru[i] == 0:\n",
    "                all_zero.append((i, 1))\n",
    "                \n",
    "        \n",
    "                \n",
    "        visited = set()\n",
    "        \n",
    "        res = [-1] * n\n",
    "        \n",
    "        max_count = 0\n",
    "        last_node = 0\n",
    "        while all_zero:\n",
    "            cur, count = all_zero.popleft()\n",
    "            last_node = cur\n",
    "            max_count = max(count, max_count)\n",
    "            visited.add(cur)\n",
    "            res[cur] = count\n",
    "            child = edges[cur]\n",
    "            ru[child] -= 1\n",
    "            if ru[child] == 0:\n",
    "                all_zero.append((child, count+1))\n",
    "                        \n",
    "        not_visited = []          \n",
    "        if len(visited) != n:\n",
    "            for i in range(n):\n",
    "                if res[i] == -1:\n",
    "                    not_visited.append(i)\n",
    "            huan_dict = dict()\n",
    "            v = set()\n",
    "            for node in not_visited:\n",
    "                if node in v:\n",
    "                    continue\n",
    "                huan = [node]\n",
    "                start = node\n",
    "                while True:\n",
    "                    v.add(node)\n",
    "                    child = edges[node]\n",
    "                    if child == start:\n",
    "                        break\n",
    "                    huan.append(child)\n",
    "                    node = child\n",
    "                huan_l = len(huan)\n",
    "                for node in huan:\n",
    "                    huan_dict[node] = huan_l\n",
    "        else:\n",
    "            not_visited = [last_node]\n",
    "            huan_dict[last_node] = 1\n",
    "            \n",
    "        \n",
    "            \n",
    "        res = [0] * n\n",
    "            \n",
    "        def dfs(node, visited, cur_count):\n",
    "            nonlocal res\n",
    "            nonlocal not_visited\n",
    "            visited.add(node)\n",
    "            res[node] = cur_count\n",
    "            for child in fan_child[node]:\n",
    "                if child in visited or child in not_visited:\n",
    "                    continue\n",
    "                dfs(child, visited, cur_count+1)\n",
    "                \n",
    "        # print(not_visited, fan_child)\n",
    "            \n",
    "        visited = set()\n",
    "        for not_v in not_visited:\n",
    "            dfs(not_v, visited, huan_dict[not_v])\n",
    "                    \n",
    "        return res\n",
    "                \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        edgesIn, degreeIn, s, res = [set() for _ in range(len(edges))], [0 for _ in range(len(edges))], set(range(len(edges))), [0 for _ in range(len(edges))]\n",
    "        for i in range(len(edges)):\n",
    "            edgesIn[edges[i]].add(i)\n",
    "            degreeIn[edges[i]] += 1\n",
    "        l = [i for i in range(len(edges)) if degreeIn[i] == 0]\n",
    "        while l:\n",
    "            pres = l.pop()\n",
    "            s.remove(pres)\n",
    "            degreeIn[edges[pres]] -= 1\n",
    "            if degreeIn[edges[pres]] == 0:\n",
    "                l.append(edges[pres])\n",
    "        se = set()\n",
    "        for x in s:\n",
    "            if res[x] == 0:\n",
    "                sp, pres = {x}, x\n",
    "                while edges[pres] not in sp:\n",
    "                    pres = edges[pres]\n",
    "                    sp.add(pres)\n",
    "                for x in sp:\n",
    "                    res[x] = len(sp)\n",
    "                se |= sp\n",
    "        while se:\n",
    "            pres = se.pop()\n",
    "            for x in edgesIn[pres]:\n",
    "                if res[x] == 0:\n",
    "                    res[x] = res[pres] + 1\n",
    "                    se.add(x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        indeg = [0] * n\n",
    "        for x in edges: indeg[x] += 1\n",
    "        q = [x for x in range(n) if indeg[x] == 0]\n",
    "        # rg = [[] for _ in range(n)]\n",
    "        while q:\n",
    "            nq = []\n",
    "            for u in q:\n",
    "                v = edges[u]\n",
    "                # rg[v].append(u)\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0: nq.append(v)\n",
    "            q = nq\n",
    "        \n",
    "        # dist = [0 if indeg[u] else -1 for u in range(n)]\n",
    "        dist = [0] * n\n",
    "        \n",
    "        def gao(u: int):\n",
    "            if dist[u]: return dist[u]\n",
    "            if indeg[u]:\n",
    "                path = []\n",
    "                while not dist[u]:\n",
    "                    path.append(u)\n",
    "                    dist[u] = -1\n",
    "                    u = edges[u]\n",
    "                for u in path:\n",
    "                    dist[u] = len(path)\n",
    "                return dist[u]\n",
    "            dist[u] = 1 + gao(edges[u])\n",
    "            return dist[u]\n",
    "\n",
    "        \n",
    "        for u in range(n):\n",
    "            gao(u)\n",
    "        \n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        deg = [0] * n\n",
    "        for u, v in enumerate(edges):\n",
    "            deg[v] += 1\n",
    "        # print(deg)\n",
    "        q = [i for i, d in enumerate(deg) if d == 0]\n",
    "        # print(q)\n",
    "        # if len(q) == 0:\n",
    "        #     return [n] * n\n",
    "        starts = q.copy()\n",
    "        while q:\n",
    "            t, q = q, []\n",
    "            for x in t:\n",
    "                y = edges[x]\n",
    "                deg[y] -= 1\n",
    "                if deg[y] <= 0:\n",
    "                    q.append(y)\n",
    "        q = [i for i, d in enumerate(deg) if d > 0]\n",
    "    \n",
    "        ans = [0] * n\n",
    "        # print(deg, starts)\n",
    "        def dfs(x):\n",
    "            if ans[x] != 0:\n",
    "                return ans[x]\n",
    "            if deg[x] > 0:\n",
    "                nodes = [x]\n",
    "                y = edges[x]\n",
    "                while y != x:\n",
    "                    nodes.append(y)\n",
    "                    y = edges[y]\n",
    "                for y in nodes:\n",
    "                    ans[y] = len(nodes)\n",
    "                # print(nodes)\n",
    "                return len(nodes)\n",
    "            ans[x] = dfs(edges[x]) + 1\n",
    "            return ans[x]\n",
    "            \n",
    "            \n",
    "        for x in starts:\n",
    "            dfs(x)\n",
    "        for x in q:\n",
    "            if deg[x] > 0:\n",
    "                dfs(x)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        rev = [0] * n\n",
    "        for i in range(n) :\n",
    "            rev[edges[i]] = i\n",
    "\n",
    "        indeg = [0] * n\n",
    "        for edge in edges :\n",
    "            indeg[edge] += 1\n",
    "        q = []\n",
    "        for i in range(n) :\n",
    "            if indeg[i] == 0 :\n",
    "                q.append(i)\n",
    "        while q :\n",
    "            p = q.pop()\n",
    "            indeg[edges[p]] -= 1\n",
    "            if indeg[edges[p]] == 0 :\n",
    "                q.append(edges[p])\n",
    "\n",
    "        ans = [0] * n\n",
    "        def calc(k) :\n",
    "            if indeg[k] == 1 :\n",
    "                return ans[k]\n",
    "            depth = calc(edges[k])\n",
    "            ans[k] = depth + 1\n",
    "            return depth + 1\n",
    "        \n",
    "        st = [False] * n\n",
    "        for i in range(n) :\n",
    "            if indeg[i] != 1 or st[i] == True :\n",
    "                continue\n",
    "            ring = []\n",
    "            k = i\n",
    "            while True :\n",
    "                ring.append(k)\n",
    "                k = edges[k]\n",
    "                st[k] = True\n",
    "                if k == i :\n",
    "                    break\n",
    "            for r in ring :\n",
    "                ans[r] = len(ring)\n",
    "        for i in range(n) :\n",
    "            if ans[i] == 0 :\n",
    "                calc(i)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        rg = collections.defaultdict(set)\n",
    "        dg = collections.defaultdict(int)\n",
    "        for a, b in enumerate(edges):\n",
    "            rg[b].add(a)\n",
    "            dg[b] += 1\n",
    "        dq = collections.deque(i for i in range(n) if dg[i] == 0)\n",
    "        while dq:\n",
    "            cur = dq.popleft()\n",
    "            ne = edges[cur]\n",
    "            dg[ne] -= 1\n",
    "            if dg[ne] == 0:\n",
    "                dq.append(ne)\n",
    "        ring_sz = [0] * n\n",
    "        for i in range(n):\n",
    "            if ring_sz[i] == 0 and dg[i] == 1:\n",
    "                collect = set()\n",
    "                cur = i\n",
    "                while cur not in collect:\n",
    "                    collect.add(cur)\n",
    "                    cur = edges[cur]\n",
    "                for i in collect:\n",
    "                    ring_sz[i] = len(collect)\n",
    "        @cache\n",
    "        def dfs(node):\n",
    "            if ring_sz[node] != 0:\n",
    "                return ring_sz[node]\n",
    "            return 1 + dfs(edges[node])\n",
    "        \n",
    "        return [dfs(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        CI = [0] * n\n",
    "    \n",
    "        @cache\n",
    "        def dfs(cur):\n",
    "            if Res[cur]:return Res[cur]\n",
    "            nxt = edges[cur]\n",
    "            v = dfs(nxt) + 1\n",
    "            Res[cur] = v\n",
    "            return v\n",
    "        \n",
    "        Res = [0] * n\n",
    "        for idx in range(n):\n",
    "            if not Res[idx]:\n",
    "                S = set()\n",
    "                cur = idx\n",
    "                f = 0\n",
    "                while cur not in S:\n",
    "                    if Res[cur]:f=1;break\n",
    "                    S.add(cur)\n",
    "                    cur = edges[cur]\n",
    "                if not f:\n",
    "                    cnt = 0\n",
    "                    S1 = set()\n",
    "                    while cur not in S1:\n",
    "                        S1.add(cur)\n",
    "                        cur = edges[cur]\n",
    "                        cnt += 1\n",
    "                    for x in S1:\n",
    "                        CI[x] = cnt\n",
    "                        Res[x] = cnt\n",
    "                dfs(idx)\n",
    "        return Res\n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        ans = [-1] * n\n",
    "        indegree = [0] * n\n",
    "        \n",
    "        visited = set()\n",
    "        \n",
    "        for st, end in enumerate(edges):\n",
    "            indegree[end] += 1\n",
    "        \n",
    "        q = deque(list(i for i, v in enumerate(indegree) if v == 0))\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            indegree[edges[node]] -= 1\n",
    "            if indegree[edges[node]] == 0:\n",
    "                q.append(edges[node])\n",
    "        \n",
    "        for i, v in enumerate(indegree):\n",
    "            if v:\n",
    "                if i not in visited:\n",
    "                    count = 1\n",
    "                    loop = [i]\n",
    "                    \n",
    "                    curr = edges[i]\n",
    "                    while curr != i:\n",
    "                        count += 1\n",
    "                        loop.append(curr)\n",
    "                        curr = edges[curr]\n",
    "                    \n",
    "                    for x in loop:\n",
    "                        ans[x] = count\n",
    "                        visited.add(x)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if ans[i] >= 0:\n",
    "                return ans[i]\n",
    "            return dfs(edges[i]) + 1\n",
    "        for i, v in enumerate(indegree):\n",
    "            ans[i] = dfs(i)\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "                \n",
    "        \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        d = {}\n",
    "        for i in range(len(edges)):\n",
    "            l, x = [], i\n",
    "            while x not in d:\n",
    "                d[x] = None\n",
    "                l.append(x)\n",
    "                x = edges[x]\n",
    "            p = len(l) if x not in l else l.index(x)\n",
    "            for x in l[:p]: d[x] = (0, -1)\n",
    "            for x in l[p:]: d[x] = (1, len(l)-p)\n",
    "\n",
    "        @cache\n",
    "        def f(x): return d[x][1] if d[x][0]==1 else 1+f(edges[x])\n",
    "\n",
    "        return [f(i) for i in range(len(d))]      \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "\n",
    "        deg = [0] * n\n",
    "        for y in edges:\n",
    "            deg[y] += 1\n",
    "\n",
    "        q = deque(i for i, d in enumerate(deg) if d == 0)\n",
    "\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            y = edges[x]\n",
    "            deg[y] -= 1\n",
    "            if deg[y] == 0:\n",
    "                q.append(y)\n",
    "\n",
    "        cycles = [i for i, d in enumerate(deg) if d != 0]\n",
    "\n",
    "        def find_cycle(x=0):\n",
    "            cycle = set()\n",
    "            while x not in cycle:\n",
    "                cycle.add(x)\n",
    "                x = edges[x]\n",
    "            return cycle\n",
    "\n",
    "        mp = {}\n",
    "        for x in cycles:\n",
    "            if x in mp:\n",
    "                continue\n",
    "            cycle = find_cycle(x)\n",
    "            size = len(cycle)\n",
    "            for y in cycle:\n",
    "                mp[y] = size\n",
    "\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x in mp:\n",
    "                return mp[x]\n",
    "            return 1 + dfs(edges[x])\n",
    "\n",
    "        return [dfs(x) for x in range(n)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        ng,rg,g=defaultdict(list),defaultdict(list),defaultdict(list)\n",
    "        deg=[0]*len(edges)\n",
    "        for i,e in enumerate(edges):\n",
    "            g[e].append(i)\n",
    "            g[i].append(e)\n",
    "            rg[e].append(i)\n",
    "            ng[i].append(e)\n",
    "            deg[e]+=1\n",
    "        \n",
    "        noloop,loop=set(),set()\n",
    "        q=deque([])\n",
    "        for e in range(len(edges)):\n",
    "            if deg[e]==0:\n",
    "                q.append(e)\n",
    "        while len(q):\n",
    "            i=q.popleft()\n",
    "            noloop.add(i)\n",
    "            j=edges[i]\n",
    "            deg[j]-=1\n",
    "            if deg[j] == 0:\n",
    "                q.append(j)\n",
    "        for i in range(len(edges)):\n",
    "            if i not in noloop:\n",
    "                loop.add(i)\n",
    "        ans=0\n",
    "        cnt={}\n",
    "        ans=[0]*len(edges)\n",
    "        for i in loop:\n",
    "            if i not in cnt:\n",
    "                c = edges[i]\n",
    "                t = 1\n",
    "                pts = [i,c]\n",
    "                while c != i:\n",
    "                    t += 1\n",
    "                    c = edges[c]\n",
    "                    if c != i:\n",
    "                        pts.append(c)\n",
    "                for pp in pts:\n",
    "                    cnt[pp] = t\n",
    "                    ans[pp] = t\n",
    "                # print(cnt)\n",
    "            ln = cnt[i]\n",
    "            br = 0\n",
    "            for j in rg[i]:\n",
    "                if j in loop: continue\n",
    "                t, c= 0, j\n",
    "                \n",
    "                def dfs(node, d):\n",
    "                    ans[node] = ln + d\n",
    "                    for u in rg[node]:\n",
    "                        dfs(u, d+1)\n",
    "                    \n",
    "                r = dfs(c, 1)\n",
    "            #     br = max(br, r)\n",
    "            # ans=max(ans,br+ln)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, g: List[int]) -> List[int]:\n",
    "        n=len(g)\n",
    "        ans=[0]*n\n",
    "        deg=[0]*n\n",
    "        s=set()\n",
    "        for w in g:\n",
    "            deg[w] += 1\n",
    "        q = deque(i for i, d in enumerate(deg) if d == 0)\n",
    "        while q:  # 拓扑排序，剪掉 g 上的所有树枝\n",
    "            v = q.popleft()\n",
    "            s.add(v)\n",
    "            w = g[v]  # v 只有一条出边\n",
    "            deg[w] -= 1\n",
    "            if deg[w] == 0:\n",
    "                q.append(w)\n",
    "        for i, d in enumerate(deg):\n",
    "            if d == 0 :\n",
    "                continue\n",
    "            # 遍历基环上的点（拓扑排序后入度大于 0）\n",
    "            deg[i] = 0\n",
    "            ring_size = 1\n",
    "            v = g[i]\n",
    "            while v != i:\n",
    "                deg[v] = 0  # 将基环上的点的入度标记为 0，避免重复访问\n",
    "                ring_size += 1\n",
    "                v = g[v]\n",
    "            ans[i]=ring_size\n",
    "            v = g[i]\n",
    "            while v != i:\n",
    "                ans[v]=ring_size\n",
    "                v = g[v]\n",
    "        for w in g:\n",
    "            deg[w] += 1\n",
    "        q = deque(i for i, d in enumerate(deg) if d == 0)\n",
    "        while q:  # 拓扑排序，剪掉 g 上的所有树枝\n",
    "            v = q.popleft()\n",
    "            s.add(v)\n",
    "            w = g[v]  # v 只有一条出边\n",
    "            deg[w] -= 1\n",
    "            if deg[w] == 0:\n",
    "                q.append(w)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res=0\n",
    "            if deg[i]==1:res+=ans[i]\n",
    "            if deg[i]==0:\n",
    "                res+=dfs(g[i])+1\n",
    "            return res\n",
    "        for v in s:\n",
    "            ans[v]=dfs(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, receiver: List[int]) -> List[int]:\n",
    "        n = len(receiver)\n",
    "        link = []\n",
    "        index = [-1] * n\n",
    "        step = [0] * n\n",
    "        nextPoint = [-1] * n\n",
    "        deg = [0] * n\n",
    "        for r in receiver:\n",
    "            deg[r] += 1\n",
    "\n",
    "        for d,i in product((0, 1),range(n)):\n",
    "            if deg[i] != d: continue\n",
    "            start = len(link)\n",
    "            while index[i] == -1:\n",
    "                deg[i] -= 1\n",
    "                index[i] = len(link)\n",
    "                link.append(i)\n",
    "                i = receiver[i]\n",
    "            if index[i] >= start:  ##遇到新的环\n",
    "                for j in range(index[i],len(link)):\n",
    "                    step[j] = len(link) - index[i]\n",
    "                    nextPoint[j] = j\n",
    "                for j in range(start,index[i]):\n",
    "                    step[j] = index[i] - j\n",
    "                    nextPoint[j] = index[i]\n",
    "            else:  # index[i] < start遇到分支\n",
    "                for j in range(start,len(link)):\n",
    "                    step[j] = len(link) - j\n",
    "                    nextPoint[j] = index[i]\n",
    "        ans=[0]*n\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            np=nextPoint[i]\n",
    "            if np==i:#在环内\n",
    "                ans[i]=step[np]\n",
    "            else:\n",
    "                ans[i]=dfs(np)+step[i]\n",
    "            return ans[i]\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        return [ans[index[i]] for i in range(n)] \n",
    "                \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, receiver: List[int]) -> List[int]:\n",
    "        n = len(receiver)\n",
    "        link = []\n",
    "        index = [-1] * n\n",
    "        step = [0] * n\n",
    "        nextPoint = [-1] * n\n",
    "        deg = [0] * n\n",
    "        for r in receiver:\n",
    "            deg[r] += 1\n",
    "\n",
    "        for d,i in product((0, 1),range(n)):\n",
    "            if deg[i] != d: continue\n",
    "            start = len(link)\n",
    "            while index[i] == -1:\n",
    "                deg[i] -= 1\n",
    "                index[i] = len(link)\n",
    "                link.append(i)\n",
    "                i = receiver[i]\n",
    "            #if index[i] >= start: 遇到新的环\n",
    "            #else: index[i] < start遇到分支\n",
    "            stones = [start, index[i], len(link)] if index[i] >= start else [start, len(link)]\n",
    "            for s, e in pairwise(stones):\n",
    "                for j in range(s, e):\n",
    "                    step[j] = e - j\n",
    "                    nextPoint[j] = index[i]\n",
    "        ans=[0]*n\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            np=nextPoint[i]\n",
    "            if nextPoint[np]==np and np<=i<np+step[np]:#在环内\n",
    "                ans[i]=step[np]\n",
    "            else:\n",
    "                ans[i]=dfs(np)+step[i]\n",
    "            return ans[i]\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        return [ans[index[i]] for i in range(n)] \n",
    "                \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        sys.setrecursionlimit(10**6)\n",
    "        qu = deque()\n",
    "        n = len(edges)\n",
    "        du = [0] * n\n",
    "        for i, x in enumerate(edges):\n",
    "            du[x]+=1\n",
    "        for i, x in enumerate(du):\n",
    "            if x == 0:\n",
    "                qu.append(i)\n",
    "        \n",
    "        while qu:\n",
    "            cur = qu.popleft()\n",
    "            x = edges[cur]\n",
    "            du[x] -= 1\n",
    "            if du[x] == 0:\n",
    "                qu.append(x)\n",
    "        \n",
    "        fa = list(range(n))\n",
    "        sz = [1] * n\n",
    "        def getfa(x):\n",
    "            root = x\n",
    "            while root != fa[root]:\n",
    "                root = fa[root]\n",
    "            while x != fa[x]:\n",
    "                fa[x], x = root, fa[x] \n",
    "            return x\n",
    "        \n",
    "        def merge(a, b):\n",
    "            pa, pb = getfa(a), getfa(b)\n",
    "            if pa != pb:\n",
    "                if sz[pb] > sz[pa]: pa, pb = pb, pa\n",
    "                sz[pb] += sz[pa]\n",
    "                sz[pa] = 0\n",
    "                fa[pa] = pb\n",
    "        \n",
    "        ans = [0] * n\n",
    "        def dfs(x):\n",
    "            if ans[x]: return ans[x]\n",
    "            if du[x] > 0: \n",
    "                ans[x] = sz[getfa(x)]\n",
    "                return ans[x]\n",
    "            y = edges[x]\n",
    "            ans[x] = dfs(y) + 1\n",
    "            return ans[x]\n",
    "    \n",
    "        for x, y in enumerate(edges):\n",
    "            if du[x] and du[y]:\n",
    "                merge(x, y)\n",
    "    \n",
    "        \n",
    "        for i in range(n):\n",
    "            if ans[i] == 0: \n",
    "                dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        sys.setrecursionlimit(10**6)\n",
    "        qu = deque()\n",
    "        n = len(edges)\n",
    "        du = [0] * n\n",
    "        for i, x in enumerate(edges):\n",
    "            du[x]+=1\n",
    "        for i, x in enumerate(du):\n",
    "            if x == 0:\n",
    "                qu.append(i)\n",
    "        \n",
    "        while qu:\n",
    "            cur = qu.popleft()\n",
    "            x = edges[cur]\n",
    "            du[x] -= 1\n",
    "            if du[x] == 0:\n",
    "                qu.append(x)\n",
    "        \n",
    "        fa = list(range(n))\n",
    "        sz = [1] * n\n",
    "        def getfa(x):\n",
    "            root = x\n",
    "            while root != fa[root]:\n",
    "                root = fa[root]\n",
    "            while x != fa[x]:\n",
    "                fa[x], x = root, fa[x] \n",
    "            return x\n",
    "        \n",
    "        def merge(a, b):\n",
    "            pa, pb = getfa(a), getfa(b)\n",
    "            if pa != pb:\n",
    "                # if sz[pb] > sz[pa]: pa, pb = pb, pa\n",
    "                sz[pb] += sz[pa]\n",
    "                sz[pa] = 0\n",
    "                fa[pa] = pb\n",
    "        \n",
    "        ans = [0] * n\n",
    "        def dfs(x):\n",
    "            if ans[x]: return ans[x]\n",
    "            if du[x] > 0: \n",
    "                ans[x] = sz[getfa(x)]\n",
    "                return ans[x]\n",
    "            y = edges[x]\n",
    "            ans[x] = dfs(y) + 1\n",
    "            return ans[x]\n",
    "    \n",
    "        for x, y in enumerate(edges):\n",
    "            if du[x] and du[y]:\n",
    "                merge(x, y)\n",
    "    \n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            if ans[i] == 0: \n",
    "                dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "'''\n",
    "基环树: 假设一个节点，要么不属于环中，要么只属于一个环\n",
    "'''\n",
    "\n",
    "class CyclicBasisTree:\n",
    "    def __init__(self, edges=[], undirected=False):\n",
    "        self.g, self.gr = defaultdict(list), defaultdict(list)\n",
    "        self.undirected = undirected\n",
    "        self.degree = Counter()\n",
    "        for x, y in edges:\n",
    "            self.g[x].append(y)\n",
    "            self.gr[y].append(x)\n",
    "            self.degree[x] = self.degree[x]\n",
    "            self.degree[y] += 1\n",
    "            if undirected: \n",
    "                self.g[y].append(x)\n",
    "                self.gr[x].append(y)\n",
    "                self.degree[x] += 1\n",
    "        self.rings = defaultdict(list)\n",
    "        self.node2ring = {}\n",
    "        self.depth = {}\n",
    "        deg = deepcopy(self.degree)\n",
    "        dq = deque()\n",
    "        self.not_ring = set()\n",
    "        for x, d in deg.items():\n",
    "            if d == int(undirected):\n",
    "                dq.append(x)\n",
    "                self.not_ring.add(x)\n",
    "        while dq:\n",
    "            x = dq.popleft()\n",
    "            for y in self.g[x]:\n",
    "                if y not in self.not_ring:\n",
    "                    deg[y] -= 1\n",
    "                    if deg[y] == int(undirected): \n",
    "                        self.not_ring.add(y)\n",
    "                        dq.append(y)\n",
    "        i = -1\n",
    "        for x in self.degree:\n",
    "            if x not in self.not_ring:\n",
    "                i += 1\n",
    "                while x not in self.depth:\n",
    "                    self.rings[i].append(x)\n",
    "                    self.node2ring[x] = i\n",
    "                    self.depth[x] = 0\n",
    "                    for y in self.g[x]:\n",
    "                        if y not in self.node2ring and y not in self.depth: x = y\n",
    "\n",
    "        for x in self.degree:\n",
    "            if x not in self.not_ring:\n",
    "                dq = deque([x])\n",
    "                ring = self.node2ring[x]\n",
    "                while dq:\n",
    "                    x = dq.popleft()\n",
    "                    print(x)\n",
    "                    for y in self.gr[x]:\n",
    "                        if y not in self.depth:\n",
    "                            self.depth[y] = self.depth[x] + 1\n",
    "                            self.node2ring[y] = ring\n",
    "                            dq.append(y)\n",
    "    \n",
    "    def get_node_depth(self, x):\n",
    "        return self.depth[x]\n",
    "    \n",
    "    def get_node_ring(self, x):\n",
    "        return self.node2ring[x]\n",
    "    \n",
    "    def get_ring_nodes(self, i):\n",
    "        return self.rings[i]\n",
    "\n",
    "# cyclic_basis_tree = CyclicBasisTree(edges=edges, undirected=False) # 有向图\n",
    "# ring_len = cyclic_basis_tree.get_ring_length(cyclic_basis_tree.get_node_ring(x)) # 获取节点所在环长\n",
    "# depth = cyclic_basis_tree.get_node_depth(x) # 获取节点深度\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        edges = [(i, x) for i, x in enumerate(edges)]\n",
    "        cbt = CyclicBasisTree(edges=edges, undirected=False)\n",
    "        n = len(edges)\n",
    "        return [cbt.get_node_depth(i) + len(cbt.get_ring_nodes(cbt.get_node_ring(i))) for i in range(n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, g: List[int]) -> List[int]:\n",
    "        n=len(g)\n",
    "        ans=[0]*n\n",
    "        deg=[0]*n\n",
    "        s=set()\n",
    "        for w in g:\n",
    "            deg[w] += 1\n",
    "        q = deque(i for i, d in enumerate(deg) if d == 0)\n",
    "        while q:  # 拓扑排序，剪掉 g 上的所有树枝\n",
    "            v = q.popleft()\n",
    "            s.add(v)\n",
    "            w = g[v]  # v 只有一条出边\n",
    "            deg[w] -= 1\n",
    "            if deg[w] == 0:\n",
    "                q.append(w)\n",
    "        for i, d in enumerate(deg):\n",
    "            if d == 0 :\n",
    "                continue\n",
    "            # 遍历基环上的点（拓扑排序后入度大于 0）\n",
    "            ring_size = 0\n",
    "            v = i\n",
    "            while True:\n",
    "                deg[v]=0\n",
    "                ring_size += 1\n",
    "                v = g[v]\n",
    "                if v==i:\n",
    "                    break\n",
    "            while True:\n",
    "                ans[v]=ring_size\n",
    "                v = g[v]\n",
    "                if v==i:\n",
    "                    break\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res=0\n",
    "            if i not in s:res+=ans[i]#如果点在环上，返回ans[i]\n",
    "            if i in s:\n",
    "                res+=dfs(g[i])+1#点不在环上，那么答案就是dfs(g[i])+1\n",
    "            return res\n",
    "        for v in s:#更新所有不在环上的点\n",
    "            ans[v]=dfs(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        e = edges\n",
    "        n = len(edges)\n",
    "        e_in = [0]*n\n",
    "        \n",
    "        for i in range(n):\n",
    "            e_in[e[i]]+=1\n",
    "            \n",
    "        q = [i for i in range(n) if e_in[i]==0]\n",
    "        visited = set()\n",
    "        while q:\n",
    "            i = q.pop()\n",
    "            visited.add(i)\n",
    "            j = e[i]\n",
    "            e_in[j]-=1\n",
    "            if e_in[j]==0:\n",
    "                q.append(j)\n",
    "        \n",
    "        g = [i for i in range(n)]\n",
    "        s = [1 for _ in range(n)]\n",
    "        \n",
    "        def find(i):\n",
    "            while i!=g[i]:\n",
    "                i = g[i]\n",
    "            return i\n",
    "        \n",
    "        def union(i,j):\n",
    "            i = find(i)\n",
    "            j = find(j)\n",
    "            if i!=j:\n",
    "                if s[i]>s[j]:\n",
    "                    i,j = j,i\n",
    "                g[i] = j\n",
    "                s[j]+=s[i]\n",
    "                s[i]=0\n",
    "                \n",
    "        for i in range(n):\n",
    "            j = e[i]\n",
    "            if i not in visited and j not in visited:\n",
    "                union(i,j)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def cal(i):\n",
    "            if i not in visited:\n",
    "                return s[find(i)]\n",
    "            return 1+cal(e[i])\n",
    "        \n",
    "        return [cal(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        e = defaultdict(set)\n",
    "        for i in range(n):\n",
    "            u,v = i,edges[i]\n",
    "            e[u].add(v)\n",
    "            e[v].add(u)\n",
    "        b = []\n",
    "        tmp = set()\n",
    "        for i in range(n):\n",
    "            if i not in tmp:\n",
    "                q = deque()\n",
    "                q.append(i)\n",
    "                tmp.add(i)\n",
    "                vv = {i}\n",
    "                while q:\n",
    "                    cur = q.popleft()\n",
    "                    for nxt in e[cur]:\n",
    "                        if nxt not in tmp:\n",
    "                            tmp.add(nxt)\n",
    "                            q.append(nxt)\n",
    "                            vv.add(nxt)\n",
    "                b.append(vv)\n",
    "                \n",
    "        \n",
    "        ans = [0 for _ in range(n)]\n",
    "        def get(edges,limit):\n",
    "            d = [0 for _ in range(n)]\n",
    "            re = defaultdict(set)\n",
    "            rd = [0 for _ in range(n)]\n",
    "            for i in range(n):\n",
    "                u,v = i,edges[i]\n",
    "                d[v] += 1\n",
    "                re[v].add(u)\n",
    "                rd[u] += 1\n",
    "            non_c = set()\n",
    "            q = deque()\n",
    "            for i in limit:\n",
    "                if d[i] == 0:\n",
    "                    q.append(i)\n",
    "            while q:\n",
    "                cur = q.popleft()\n",
    "                non_c.add(cur)\n",
    "                for nxt in e[cur]:\n",
    "                    d[nxt] -= 1\n",
    "                    if d[nxt] == 0:\n",
    "                        q.append(nxt)\n",
    "            for i in limit:\n",
    "                if i not in non_c:\n",
    "                    ans[i] = len(limit) - len(non_c)\n",
    "            dp = [0 for _ in range(n)]\n",
    "            q = deque()\n",
    "            for i in limit:\n",
    "                if i not in non_c:\n",
    "                    for lst in re[i]:\n",
    "                        if lst in non_c:\n",
    "                            dp[lst] = 1\n",
    "                            q.append(lst)\n",
    "            while q:\n",
    "                cur = q.popleft()\n",
    "                for lst in re[cur]:\n",
    "                    rd[lst] -= 1\n",
    "                    dp[lst] += dp[cur]\n",
    "                    if rd[lst] == 0:\n",
    "                        dp[lst] += 1\n",
    "                        q.append(lst)\n",
    "            for i in limit:\n",
    "                ans[i] += dp[i]\n",
    "                if i in non_c:\n",
    "                    ans[i] += len(limit) - len(non_c)\n",
    "            return\n",
    "    \n",
    "        for c in b:\n",
    "            limit = set(c)\n",
    "            get(edges,limit)\n",
    "            \n",
    "        return ans\n",
    "  \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        G = defaultdict(list)\n",
    "        n = len(edges)\n",
    "        I = [0] * n\n",
    "        for idx,i in enumerate(edges):\n",
    "            G[idx] = i\n",
    "            I[i] += 1\n",
    "        \n",
    "        CI = [0] * n\n",
    "        \n",
    "        \n",
    "            \n",
    "        vis = [0] * n\n",
    "        @cache\n",
    "        def dfs(cur):\n",
    "            if CI[cur]:return CI[cur]\n",
    "            nxt = G[cur]\n",
    "            v = dfs(nxt) + 1\n",
    "            Res[cur] = v\n",
    "            vis[cur] = 1\n",
    "            return v\n",
    "        Res = [0] * n\n",
    "        for idx in range(n):\n",
    "            if not vis[idx]:\n",
    "                vis[idx] = 1\n",
    "                S = set()\n",
    "                cur = idx\n",
    "                f = 0\n",
    "                while cur not in S:\n",
    "                    if CI[cur]:f=1;break\n",
    "                    S.add(cur)\n",
    "                    cur = G[cur]\n",
    "                if f:dfs(idx);continue\n",
    "                cnt = 0\n",
    "                S1 = set()\n",
    "                while cur not in S1:\n",
    "                    S1.add(cur)\n",
    "                    cur = G[cur]\n",
    "                    cnt += 1\n",
    "                for x in S1:\n",
    "                    vis[x] = 1\n",
    "                    CI[x] = cnt\n",
    "                    Res[x] = cnt\n",
    "                dfs(idx)\n",
    "        return Res\n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        deg = [0] * n\n",
    "        ans = [0] * n\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            deg[edges[i]] += 1\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if deg[i] == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            s.add(cur)\n",
    "            deg[edges[cur]] -= 1\n",
    "            if deg[edges[cur]] == 0:\n",
    "                q.append(edges[cur])\n",
    "        for i in range(n):\n",
    "            if deg[i] != 1:\n",
    "                continue\n",
    "            if ans[i] != 0:\n",
    "                continue\n",
    "            cnt = 1\n",
    "            cur = i\n",
    "            while edges[cur] != i:\n",
    "                cnt += 1\n",
    "                cur = edges[cur]\n",
    "            ans[i] = cnt\n",
    "            cur = i\n",
    "            while edges[cur] != i:\n",
    "                ans[cur] = cnt\n",
    "                cur = edges[cur]\n",
    "        # 处理非环上节点\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 0\n",
    "            nxt = edges[i]\n",
    "            if nxt not in s:\n",
    "                ans[i] = ans[nxt] + 1\n",
    "                return\n",
    "            else:\n",
    "                dfs(nxt)\n",
    "                ans[i] = ans[nxt] + 1\n",
    "        for i in range(n):\n",
    "            if ans[i] != 0:\n",
    "                continue\n",
    "            dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        deg = [0] * n\n",
    "        ans = [0] * n\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            deg[edges[i]] += 1\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if deg[i] == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            s.add(cur)\n",
    "            deg[edges[cur]] -= 1\n",
    "            if deg[edges[cur]] == 0:\n",
    "                q.append(edges[cur])\n",
    "        for i in range(n):\n",
    "            if deg[i] != 1:\n",
    "                continue\n",
    "            deg[i] = 0\n",
    "            cnt = 1\n",
    "            cur = i\n",
    "            while edges[cur] != i:\n",
    "                deg[cur] = 0\n",
    "                cnt += 1\n",
    "                cur = edges[cur]\n",
    "            ans[i] = cnt\n",
    "            cur = i\n",
    "            while edges[cur] != i:\n",
    "                ans[cur] = cnt\n",
    "                cur = edges[cur]\n",
    "        # 处理非环上节点\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 0\n",
    "            nxt = edges[i]\n",
    "            if nxt not in s:\n",
    "                ans[i] = ans[nxt] + 1\n",
    "                return\n",
    "            else:\n",
    "                dfs(nxt)\n",
    "                ans[i] = ans[nxt] + 1\n",
    "        for i in range(n):\n",
    "            if ans[i] != 0:\n",
    "                continue\n",
    "            dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class nums:\n",
    "    \"一个用二进制数字集合，该集合仅可储存[0, max_val)以内的整数，用bytearray节约内存\"\n",
    "\n",
    "    __slots__ = (\"max_val\", \"nums\", \"cnt\", \"cnts\")\n",
    "    \n",
    "    def __init__(self, max_val):\n",
    "        self.max_val = max_val\n",
    "        self.nums = bytearray((max_val >> 3) + (0 if max_val&7 == 0 else 1))\n",
    "        self.cnt = 0\n",
    "        self.cnts = [0]*10\n",
    "\n",
    "    def clear(self):\n",
    "        if self.cnt:\n",
    "            for inx, i in enumerate(self.cnts):\n",
    "                if i:\n",
    "                    a = self.max_val//10+1\n",
    "                    self.nums[inx*a: (inx+1)*a] = bytearray(a)\n",
    "            # self.nums = bytearray(len(self.nums))\n",
    "            self.cnt = 0\n",
    "            self.cnts = [0]*10\n",
    "\n",
    "    def _set(self, inx, val):\n",
    "        if not 0 <= inx < self.max_val:\n",
    "            raise IndexError(inx)\n",
    "        a, b = inx>>3, inx&7\n",
    "        if bool(self.nums[a] & (1<<b)) == val:\n",
    "            return # (inx in self and val == 1) or (inx not in self and val == 0)\n",
    "        if val:\n",
    "            self.nums[a] |= 1<<b\n",
    "            self.cnt += 1\n",
    "            self.cnts[a//(self.max_val//10+1)] += 1\n",
    "        else:\n",
    "            self.nums[a] ^= 1<<b\n",
    "            self.cnt -= 1\n",
    "            self.cnts[a//(self.max_val//10+1)] -= 1\n",
    "\n",
    "    def put(self, val):\n",
    "        self._set(val, 1)\n",
    "\n",
    "    def remove(self, val):\n",
    "        self._set(val, 0)\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        if type(self) != type(other):\n",
    "            return NotImplemented\n",
    "        return self.max_val == other.max_val and self.nums == other.nums\n",
    "\n",
    "    def __contains__(self, inx):\n",
    "        return 0 <= inx < self.max_val and bool(self.nums[inx>>3]&(1<<(inx&7)))\n",
    "\n",
    "    def __iter__(self):\n",
    "        return (inx<<3|j for inx, i in enumerate(self.nums) if i \n",
    "                         for j in range(8) if i&(1<<j))\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"nums(max_val={self.max_val}, values={list(self) if self.max_val < 10**7 else '...'})\"\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.cnt\n",
    "\n",
    "        \n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        self.edges = edges\n",
    "        self.nums = [-1]*len(edges)\n",
    "        self.t = nums(10**5)\n",
    "        for i in range(len(edges)):\n",
    "            self.t.clear()\n",
    "            self.start = i\n",
    "            self.dfs(i)\n",
    "        return self.nums\n",
    "    \n",
    "    def dfs(self, x):\n",
    "        if self.nums[x] != -1:\n",
    "            return self.nums[x]\n",
    "        if x in self.t:\n",
    "            f = len(self.t)\n",
    "            while self.start != x:\n",
    "                self.t.remove(self.start)\n",
    "                self.start = self.edges[self.start]\n",
    "                f -= 1\n",
    "            for i in range(len(self.edges)):\n",
    "                if i in self.t and self.nums[i] == -1:\n",
    "                    self.nums[i] = f\n",
    "            return f\n",
    "        self.t.put(x)\n",
    "        a = self.edges[x]\n",
    "        res = self.dfs(a)\n",
    "        if self.nums[x] == -1:\n",
    "            self.nums[x] = res+1\n",
    "            return res+1\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class nums:\n",
    "    \"一个用二进制数字集合，该集合仅可储存[0, max_val)以内的整数，用bytearray节约内存\"\n",
    "\n",
    "    __slots__ = (\"max_val\", \"nums\", \"cnt\")\n",
    "    \n",
    "    def __init__(self, max_val):\n",
    "        self.max_val = max_val\n",
    "        self.nums = bytearray((max_val >> 3) + (0 if max_val&7 == 0 else 1))\n",
    "        self.cnt = 0\n",
    "\n",
    "    def clear(self):\n",
    "        if self.cnt:\n",
    "            self.nums = bytearray(len(self.nums))\n",
    "            self.cnt = 0\n",
    "\n",
    "    def put(self, val):\n",
    "        if not 0 <= val < self.max_val:\n",
    "            raise IndexError(val)\n",
    "        a, b = val>>3, val&7\n",
    "        if self.nums[a] & (1<<b):\n",
    "            return  # val in self\n",
    "        self.nums[a] |= 1<<b\n",
    "        self.cnt += 1\n",
    "\n",
    "    def remove(self, val):\n",
    "        if not 0 <= val < self.max_val:\n",
    "            raise IndexError(val)\n",
    "        a, b = val>>3, val&7\n",
    "        if not self.nums[a] & (1<<b):\n",
    "            return  # val not in self\n",
    "        self.nums[a] ^= 1<<b\n",
    "        self.cnt -= 1\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        if type(self) != type(other):\n",
    "            return NotImplemented\n",
    "        return self.max_val == other.max_val and self.nums == other.nums\n",
    "\n",
    "    def __contains__(self, val):\n",
    "        return 0 <= val < self.max_val and bool(self.nums[val>>3]&(1<<(val&7)))\n",
    "\n",
    "    def __iter__(self):\n",
    "        return (inx<<3|j for inx, i in enumerate(self.nums) if i \n",
    "                         for j in range(8) if i&(1<<j))\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"nums(max_val={self.max_val}, values={list(self) if self.max_val < 10**7 else '...'})\"\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.cnt\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        self.edges = edges\n",
    "        self.nums = [-1]*len(edges)\n",
    "        self.t = nums(10**5)\n",
    "        for i in range(len(edges)):\n",
    "            self.t.clear()\n",
    "            self.start = i\n",
    "            self.dfs(i)\n",
    "        return self.nums\n",
    "    \n",
    "    def dfs(self, x):\n",
    "        if self.nums[x] != -1:\n",
    "            return self.nums[x]\n",
    "        if x in self.t:\n",
    "            f = len(self.t)\n",
    "            while self.start != x:\n",
    "                self.t.remove(self.start)\n",
    "                self.start = self.edges[self.start]\n",
    "                f -= 1\n",
    "            for i in range(len(self.edges)):\n",
    "                if i in self.t and self.nums[i] == -1:\n",
    "                    self.nums[i] = f\n",
    "            return f\n",
    "        self.t.put(x)\n",
    "        a = self.edges[x]\n",
    "        res = self.dfs(a)\n",
    "        if self.nums[x] == -1:\n",
    "            self.nums[x] = res+1\n",
    "            return res+1\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        N = len(edges)\n",
    "        answer = [None] * N\n",
    "        def get_count(i, fast):\n",
    "            if answer[i] is not None:\n",
    "                return answer[i]\n",
    "            if i == fast:\n",
    "                c = 0\n",
    "                while True:\n",
    "                    fast = edges[fast]\n",
    "                    c += 1\n",
    "                    if fast == i:\n",
    "                        break\n",
    "                while True:\n",
    "                    fast = edges[fast]\n",
    "                    answer[fast] = c\n",
    "                    if fast == i:\n",
    "                        break\n",
    "                return c\n",
    "            else:\n",
    "                c = get_count(edges[i], edges[edges[fast]])\n",
    "                if answer[i] is not None:\n",
    "                    return answer[i]\n",
    "                else:\n",
    "                    answer[i] = c + 1\n",
    "                    return answer[i]\n",
    "        for i in range(N):\n",
    "            get_count(i, edges[i])\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class nums:\n",
    "    __slots__ = (\"max_val\", \"nums\", \"t\")\n",
    "    def __init__(self, max_val, t=10):\n",
    "        self.max_val = max_val\n",
    "        p = max_val/(1<<t)\n",
    "        self.nums = [0]*(int(p) if int(p) == p else int(p)+1)\n",
    "        self.t = t\n",
    "\n",
    "    def _set(self, inx, val):\n",
    "        if inx >= self.max_val:\n",
    "            raise IndexError(inx)\n",
    "        if val not in (0, 1):\n",
    "            raise ValueError(val)\n",
    "        a, b = inx>>self.t, inx&((1<<self.t)-1)\n",
    "        self.nums[a] |= 1<<b\n",
    "        if not val:\n",
    "            self.nums[a] ^= 1<<b\n",
    "\n",
    "    def put(self, val):\n",
    "        self._set(val, 1)\n",
    "\n",
    "    def remove(self, val):\n",
    "        self._set(val, 0)\n",
    "\n",
    "    def __hash__(self):\n",
    "        res = hash(self.max_val)^hash(self.t)\n",
    "        for i in nums:\n",
    "            res ^= hash(i)\n",
    "        return res\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        if type(self) != type(other):\n",
    "            return NotImplemented\n",
    "        if self.t != other.t:\n",
    "            return False\n",
    "        if self.max_val != other.max_val:\n",
    "            return False\n",
    "        return all(i == j for i, j in zip(self.nums, other.nums))\n",
    "\n",
    "    def __contains__(self, inx):\n",
    "        if inx >= self.max_val:\n",
    "            raise IndexError(inx)\n",
    "        a, b = inx>>self.t, inx&((1<<self.t)-1)\n",
    "        return bool(self.nums[a]&(1<<b))\n",
    "\n",
    "    def __iter__(self):\n",
    "        for inx, i in enumerate(self.nums):\n",
    "            if self.nums[inx]:\n",
    "                v = inx<<self.t\n",
    "                for j in range(1<<self.t):\n",
    "                    if i&(1<<j):\n",
    "                        yield v+j\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"nums(max_val={self.max_val}, values={list(self)})\"\n",
    "\n",
    "    def __len__(self):\n",
    "        return sum([i.bit_count() for i in self.nums])\n",
    "        \n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        self.edges = edges\n",
    "        self.nums = [-1]*len(edges)\n",
    "        for i in range(len(edges)):\n",
    "            self.t = set()\n",
    "            self.start = i\n",
    "            self.dfs(i)\n",
    "        return self.nums\n",
    "    \n",
    "    def dfs(self, x):\n",
    "        if self.nums[x] != -1:\n",
    "            return self.nums[x]\n",
    "        if x in self.t:\n",
    "            f = len(self.t)\n",
    "            while self.start != x and f:\n",
    "                self.t.remove(self.start)\n",
    "                self.start = self.edges[self.start]\n",
    "                f -= 1\n",
    "            for i in range(len(self.edges)):\n",
    "                if i in self.t and self.nums[i] == -1:\n",
    "                    self.nums[i] = f\n",
    "            return f\n",
    "        self.t.add(x)\n",
    "        a = self.edges[x]\n",
    "        res = self.dfs(a)\n",
    "        if self.nums[x] == -1:\n",
    "            self.nums[x] = res+1\n",
    "            return res+1\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs1(edges, now, steps, target):\n",
    "    # print(now, target)\n",
    "    if now == target:\n",
    "        return steps\n",
    "    return dfs1(edges, edges[now], steps + 1, target)\n",
    "\n",
    "def dfs2(edges, now, steps, lenth, ans):\n",
    "    if lenth == 0:\n",
    "        return ans\n",
    "    ans[now] = steps\n",
    "    return dfs2(edges, edges[now], steps, lenth - 1, ans)\n",
    "\n",
    "def dfs3(edges, i, ans):\n",
    "    if ans[i]:\n",
    "        return ans\n",
    "    ans = dfs3(edges, edges[i], ans)\n",
    "    ans[i] = ans[edges[i]] + 1\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        points = len(edges)\n",
    "        in_edges = [0 for i in range(len(edges))]\n",
    "        for i in edges:\n",
    "            in_edges[i] += 1\n",
    "        q = []\n",
    "        for i in range(points):\n",
    "            if in_edges[i] == 0:\n",
    "                q.append(i)\n",
    "        while len(q):\n",
    "            now = q.pop()\n",
    "            in_edges[edges[now]] -= 1\n",
    "            if in_edges[edges[now]] == 0:\n",
    "                q.append(edges[now])\n",
    "        \n",
    "\n",
    "        ans = [0 for i in range(points)]\n",
    "        for i in range(points):\n",
    "            if in_edges[i] and ans[i] == 0:\n",
    "                dis = dfs1(edges, edges[i], 1, i)\n",
    "                # print(\"dis:\", dis)\n",
    "                ans = dfs2(edges, i, dis, dis, ans)\n",
    "                # print(\"ans\", ans)\n",
    "        \n",
    "        for i in range(points):\n",
    "            if ans[i] == 0:\n",
    "                ans = dfs3(edges, i, ans)\n",
    "\n",
    "        print(ans)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, e: List[int]) -> List[int]:\n",
    "        n = len(e)\n",
    "        ans = [0] * n\n",
    "        f = [0] * n\n",
    "        \n",
    "        def dfs(k, t):\n",
    "            f[k] = t\n",
    "            if ans[e[k]] > 0:\n",
    "                ans[k] = ans[e[k]] + 1\n",
    "                return n + 1\n",
    "            if f[e[k]] > 0:\n",
    "                ans[k] = t - f[e[k]] + 1\n",
    "                return f[e[k]]\n",
    "            r = dfs(e[k], t + 1)\n",
    "            ans[k] = ans[e[k]]\n",
    "            if t < r:\n",
    "                ans[k] += 1\n",
    "            return r\n",
    "            \n",
    "        for i in range(n):\n",
    "            if ans[i] == 0:\n",
    "                dfs(i, 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(edges)\n",
    "        d = [0] * n\n",
    "        cnt = [0] * n\n",
    "        vis = [False] * n\n",
    "        for i, x in enumerate(edges):\n",
    "            d[x] += 1\n",
    "        \n",
    "        q = deque()\n",
    "        for i, x in enumerate(edges):\n",
    "            if d[i] == 0:\n",
    "                q.append(i)\n",
    "                \n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            vis[t] = True\n",
    "            d[edges[t]] -= 1\n",
    "            if d[edges[t]] == 0:\n",
    "                q.append(edges[t])\n",
    "           \n",
    "        def dfs(x):\n",
    "            nonlocal tot\n",
    "            tot += 1\n",
    "            vis[x] = True\n",
    "            if not vis[edges[x]]:\n",
    "                dfs(edges[x])\n",
    "            cnt[x] = tot\n",
    "                \n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                tot = 0\n",
    "                dfs(i)\n",
    "                \n",
    "        d = [0] * n       \n",
    "        for i, x in enumerate(edges):\n",
    "            d[x] += 1\n",
    "    \n",
    "        def dfs1(x):\n",
    "            if not cnt[edges[x]]:\n",
    "                dfs1(edges[x])\n",
    "            cnt[x] = cnt[edges[x]] + 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if d[i] == 0:\n",
    "                dfs1(i)\n",
    "      \n",
    "        \n",
    "        return cnt  \n",
    "        \n",
    "# [3,6,1,0,5,7,4,3]\n",
    "# [2,7,8,2,5,4,6,3]               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def countVisitedNodes(self, edges):\n",
    "      n = len(edges)\n",
    "      ans = [-1] * n \n",
    "      # loop = dict() # 一开始我以为只记录环就行，其实环外的点也可以添加\n",
    "      def dfs(i, path):\n",
    "                    # elif i in loop: # 遇到之前搜过的节点\n",
    "          if ans[i] != -1: # 遇到之前搜过的节点\n",
    "              for j in path:  # 肯定不在环内 ? 在环内也没事\n",
    "                  # ans[j] = loop[i] + len(path) - path[j]\n",
    "                  ans[j] = ans[i] + len(path) - path[j]\n",
    "                  # loop[j] = ans[j]\n",
    "              return \n",
    "          if i in path: # 遇到环了\n",
    "              lenloop = len(path)-path[i] # 环的长度\n",
    "              for j in path:  # 路径上的每个节点添加进答案\n",
    "                  if path[j]>=path[i]: # 如果节点在环内，则为环的长度\n",
    "                      ans[j] = lenloop \n",
    "                      # loop[j] = lenloop\n",
    "                  else:   # 在环外则为节点在搜索路径的位置到路径终点的距离\n",
    "                      ans[j] = len(path)-path[j] \n",
    "                      # loop[j] = ans[j]\n",
    "              return\n",
    "\n",
    "          # 还没遇到环或者之前搜过的节点，加入路径，继续搜索\n",
    "          path[i] = len(path) \n",
    "          return dfs(edges[i], path)\n",
    "\n",
    "      # 遍历，搜过不用再搜\n",
    "      for i in range(n):\n",
    "          if ans[i]==-1: \n",
    "              path = dict()\n",
    "              dfs(i, path)\n",
    "      \n",
    "      return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        st = [-1] * n\n",
    "        ans = [0] * n\n",
    "        tmp = []\n",
    "        p = 0\n",
    "        def dfs(u:int)->None:\n",
    "            nonlocal p\n",
    "            if(ans[u]) :return \n",
    "            if(st[u]!=-1):\n",
    "                t=p-st[u]\n",
    "                while(tmp[-1]!=u):\n",
    "                    ans[tmp[-1]]=t\n",
    "                    tmp.pop()\n",
    "                ans[u]=t\n",
    "                tmp.pop()\n",
    "                return \n",
    "            else:\n",
    "                tmp.append(u)\n",
    "                st[u]=p\n",
    "                p+=1\n",
    "                dfs(edges[u])\n",
    "            if(not ans[u]) :ans[u]=ans[edges[u]]+1\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        # print(edges)\n",
    "        # print(list(range(len(edges))))\n",
    "        l = []\n",
    "        m = {}\n",
    "\n",
    "        n = len(edges)\n",
    "        ans = [-1] * n\n",
    "        \n",
    "        def dfs(n,count):\n",
    "            # print('here',n)\n",
    "            nonlocal ans,l,m\n",
    "            if ans[n] != -1:\n",
    "                # print('here1',count, ans,ans[n])\n",
    "                return ans[n]\n",
    "            \n",
    "            if n in m:\n",
    "                # print(l,m[n],count)\n",
    "                for v in reversed(l):\n",
    "                    ans[v] = count - m[n]\n",
    "                    # print(ans)\n",
    "                    if v == n:\n",
    "                        return 0\n",
    "                \n",
    "            l.append(n)\n",
    "            m[n] = count\n",
    "            return 1 + dfs(edges[n],count + 1)\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            # print(ans, i)\n",
    "            if ans[i] == -1:\n",
    "                \n",
    "                l = []\n",
    "                m = {}\n",
    "                temp = dfs(i, 0)\n",
    "                if ans[i] == -1:\n",
    "                    ans[i] = temp\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,u):\n",
    "        if self.res[u] >= 0:\n",
    "            return self.res[u]\n",
    "        c = 1\n",
    "        for v in self.g[u]:\n",
    "            c += self.dfs(v)\n",
    "        self.res[u] = c\n",
    "        return c\n",
    "    \n",
    "    def color(self,u,c):\n",
    "        self.colors[u] = c\n",
    "        #print(u,c)\n",
    "        for v in self.g[u]:\n",
    "            if self.colors[v] < 0:\n",
    "                self.color(v,c)\n",
    "\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        self.n = len(edges)\n",
    "        self.g = [[] for _ in range(self.n)]\n",
    "        self.in_d = [0]*self.n\n",
    "        self.res = [-1]*self.n\n",
    "        self.colors = [-1]*self.n\n",
    "        self.color_num = 0\n",
    "\n",
    "        for u in range(self.n):\n",
    "            v = edges[u]\n",
    "            self.in_d[v] += 1\n",
    "            self.g[u].append(v)\n",
    "        \n",
    "        q = []\n",
    "        for u in range(self.n):\n",
    "            if self.in_d[u] == 0:\n",
    "                q.append(u)\n",
    "        while len(q):\n",
    "            u = q[-1]\n",
    "            q.pop()\n",
    "            for v in self.g[u]:\n",
    "                self.in_d[v] -= 1\n",
    "                if self.in_d[v] == 0:\n",
    "                    q.append(v)\n",
    "        c1 = 0           \n",
    "        for u in range(self.n):\n",
    "            if self.in_d[u] > 0 and self.colors[u]<0:\n",
    "                self.color(u, self.color_num)\n",
    "                self.color_num += 1\n",
    "\n",
    "        self.mp = {}\n",
    "        for u in range(self.n):\n",
    "            co = self.colors[u]\n",
    "            if co >= 0:\n",
    "                if co not in self.mp:\n",
    "                    self.mp[co] = 0\n",
    "                self.mp[co] += 1\n",
    "\n",
    "        for u in range(self.n):\n",
    "            co = self.colors[u]\n",
    "            if co >= 0:\n",
    "                cn = self.mp[co]\n",
    "                self.res[u] = cn\n",
    "                \n",
    "        #print(self.mp)\n",
    "\n",
    "        for u in range(self.n):\n",
    "            self.res[u] = self.dfs(u)\n",
    "\n",
    "        return self.res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(edges)\n",
    "        f = [0] * n\n",
    "        t = [0] * n\n",
    "        \n",
    "        def df(i, x):\n",
    "            if f[i] > 0:\n",
    "                return f[i]\n",
    "            \n",
    "            if t[i] > 0:\n",
    "                j = edges[i]\n",
    "                while j != i:\n",
    "                    f[j] = x - t[i]\n",
    "                    j = edges[j]\n",
    "                f[i] = x - t[i]\n",
    "                return f[i]\n",
    "            \n",
    "            t[i] = x\n",
    "            y = df(edges[i], x + 1)\n",
    "            if not f[i]:\n",
    "                f[i] = y + 1\n",
    "\n",
    "            t[i] = 0\n",
    "            return f[i]\n",
    "        \n",
    "        for i in range(n):\n",
    "            df(i, 1)\n",
    "        \n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.sz = [1] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if x != self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def merge(self, x, y):\n",
    "        fx = self.find(x)\n",
    "        fy = self.find(y)\n",
    "        if fx != fy:\n",
    "            self.fa[fx] = fy\n",
    "            self.sz[fy] += self.sz[fx]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        vis = set()\n",
    "        deg = [0] * n\n",
    "\n",
    "        for x in edges:\n",
    "            deg[x] += 1\n",
    "        \n",
    "        q = deque(i for i, d in enumerate(deg) if d == 0)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            vis.add(x)\n",
    "            y = edges[x]\n",
    "            deg[y] -= 1\n",
    "            if deg[y] == 0:\n",
    "                q.append(y)\n",
    "\n",
    "        uf = UF(n)\n",
    "        for i in range(n):\n",
    "            if i not in vis:\n",
    "                uf.merge(i, edges[i])\n",
    "\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            if i not in vis:\n",
    "                ans[i] = uf.sz[uf.find(i)]\n",
    "        \n",
    "        def f(cur):\n",
    "            if ans[cur] != 0:\n",
    "                return ans[cur]\n",
    "            ans[cur] += 1 + f(edges[cur])\n",
    "            return ans[cur]\n",
    "\n",
    "        for i in range(n):\n",
    "            if i in vis:\n",
    "                f(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        vis = defaultdict(int)\n",
    "        total = set()\n",
    "        def dfs(root, cnt):\n",
    "            if(root in vis or root in total):\n",
    "                return root\n",
    "            vis[root] = cnt\n",
    "            return dfs(edges[root], cnt+1)\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            vis.clear()\n",
    "            if(i not in total):\n",
    "                cur = dfs(i, 0)\n",
    "                if(cur in total):\n",
    "                    for num in vis.keys():\n",
    "                        ans[num] = len(vis)-vis[num]+ans[cur]\n",
    "                else:\n",
    "                    idx = vis[cur]\n",
    "                    circle_len = len(vis) - idx\n",
    "                    for num, j in vis.items():\n",
    "                        if j < idx:\n",
    "                            ans[num] = len(vis)-vis[num]\n",
    "                        else:\n",
    "                            ans[num] = circle_len\n",
    "            total.update(vis)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, g: List[int]) -> List[int]:\n",
    "        n = len(g)\n",
    "        rg = [[] for _ in range(n)]  # 反图，用于从基环遍历树枝\n",
    "        deg = [0] * n\n",
    "        for x, y in enumerate(g):\n",
    "            rg[y].append(x)\n",
    "            deg[y] += 1\n",
    "        # 分离基环和树枝\n",
    "        # 由于deg 值为 1 的点必定在基环上，为 0 的点必定在树枝上。因此拓扑排序，剪掉 g 上的所有树枝。\n",
    "        q = deque(i for i, d in enumerate(deg) if d == 0)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            y = g[x]\n",
    "            deg[y] -= 1\n",
    "            if deg[y] == 0:\n",
    "                q.append(y)\n",
    "\n",
    "        ans = [0] * n\n",
    "        # 在反图上遍历树枝\n",
    "        def dfs(x: int, depth: int) -> None:\n",
    "            ans[x] = depth\n",
    "            for y in rg[x]:\n",
    "                if deg[y] == 0:  # 只遍历树枝，不遍历基环，基环已经处理过了\n",
    "                    dfs(y, depth + 1)\n",
    "        \n",
    "        vis = set()\n",
    "        for i, d in enumerate(deg):\n",
    "            if i in vis or d == 0: # 不处理树枝，只在后面的 dfs 处处理树枝\n",
    "                continue\n",
    "            vis.add(i)\n",
    "            vs = set()\n",
    "            # 收集在基环上的点\n",
    "            def dfs2(j, is_first=False):\n",
    "                if j == i and not is_first: return\n",
    "                vs.add(j)\n",
    "                vis.add(j)\n",
    "                dfs2(g[j])\n",
    "            dfs2(i, True)\n",
    "            cnt = len(vs)\n",
    "            for x in vs:\n",
    "                ans[x] = cnt\n",
    "                dfs(x, cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, g: List[int]) -> List[int]:\n",
    "        n = len(g)\n",
    "        rg = [[] for _ in range(n)]  # 反图，用于从基环遍历树枝\n",
    "        deg = [0] * n\n",
    "        for x, y in enumerate(g):\n",
    "            rg[y].append(x)\n",
    "            deg[y] += 1\n",
    "        # 分离基环和树枝\n",
    "        # 由于deg 值为 1 的点必定在基环上，为 0 的点必定在树枝上。因此拓扑排序，剪掉 g 上的所有树枝。\n",
    "        q = deque(i for i, d in enumerate(deg) if d == 0)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            y = g[x]\n",
    "            deg[y] -= 1\n",
    "            if deg[y] == 0:\n",
    "                q.append(y)\n",
    "\n",
    "        ans = [0] * n\n",
    "        # 在反图上遍历树枝\n",
    "        def dfs(x: int, depth: int) -> None:\n",
    "            ans[x] = depth\n",
    "            for y in rg[x]:\n",
    "                if deg[y] == 0:  # 只遍历树枝，不遍历基环，基环已经处理过了\n",
    "                    dfs(y, depth + 1)\n",
    "        \n",
    "        vis = set()\n",
    "        for i, d in enumerate(deg):\n",
    "            if i in vis or d == 0: # 不处理树枝，只在后面的 dfs 处处理树枝\n",
    "                continue\n",
    "            vs = set()\n",
    "            # 收集在基环上的点\n",
    "            def dfs2(j):\n",
    "                if j in vis: return\n",
    "                vs.add(j)\n",
    "                vis.add(j)\n",
    "                dfs2(g[j])\n",
    "            dfs2(i)\n",
    "            vis.add(i)\n",
    "            cnt = len(vs)\n",
    "            for x in vs:\n",
    "                ans[x] = cnt\n",
    "                dfs(x, cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        clock = [-1] * n\n",
    "        f = [0] * n\n",
    "\n",
    "        ###最多一个环\n",
    "\n",
    "        ###先找到环，然后给环赋值\n",
    "        map = [[] for i in range(n)]\n",
    "        for i, v in enumerate(edges):\n",
    "            map[v].append(i)\n",
    "\n",
    "        begin = 0\n",
    "\n",
    "        ###第一遍，先找到环，给环f赋值\n",
    "\n",
    "        def dfs(index):\n",
    "            for next in map[index]:\n",
    "                if f[next] == 0:\n",
    "                    f[next] = f[index] + 1\n",
    "                    dfs(next)\n",
    "\n",
    "        def dfs2(index, min, size):\n",
    "            if clock[index] >= min and f[index] == 0:\n",
    "                f[index] = size\n",
    "                for next in map[index]:\n",
    "                    dfs2(next, min, size)\n",
    "\n",
    "        for index in range(n):\n",
    "            first = begin\n",
    "            while clock[index] == -1:\n",
    "                clock[index] = begin\n",
    "                begin += 1\n",
    "                index = edges[index]\n",
    "            if clock[index] >= first:\n",
    "                size = begin - clock[index]\n",
    "                dfs2(index, clock[index], size)\n",
    "        for i in range(n):\n",
    "            if f[i] != 0:\n",
    "                dfs(i)\n",
    "        return f\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        vis = [False] * n\n",
    "        nodes = [[0, 0] for _ in range(n)]\n",
    "\n",
    "        def dfs(x: int, c: int) -> None:\n",
    "            if vis[x]:\n",
    "                if x in d:\n",
    "                    len_rings = c - d[x]\n",
    "                    for y in d:\n",
    "                        nodes[y] = [len_rings, max(d[x] - d[y], 0)]\n",
    "                else:\n",
    "                    len_rings, dist = nodes[x]\n",
    "                    len_d = len(d)\n",
    "                    for y in d:\n",
    "                        nodes[y] = [len_rings, (len_d - d[y]) + dist]\n",
    "                return\n",
    "            vis[x] = True\n",
    "            d[x] = c\n",
    "            dfs(edges[x], c + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            if vis[i]:\n",
    "                continue\n",
    "            d = {}\n",
    "            dfs(i, 0)\n",
    "        ans = [x + y for x, y in nodes]\n",
    "        print(nodes)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from functools import lru_cache\n",
    "from typing import List, Mapping, Sequence, Tuple, Union\n",
    "\n",
    "\n",
    "SequenceGraph = Sequence[Sequence[int]]\n",
    "MappingGraph = Mapping[int, Sequence[int]]\n",
    "Graph = Union[SequenceGraph, MappingGraph]\n",
    "\n",
    "\n",
    "def cyclePartition(\n",
    "    n: int, graph: Graph, isDirected: bool\n",
    ") -> Tuple[List[List[int]], List[bool], List[int], List[int]]:\n",
    "    \"\"\"返回基环树森林的环分组信息(环的大小>=2)以及每个点在拓扑排序中的最大深度.\n",
    "\n",
    "    Args:\n",
    "        - n: 图的节点数.\n",
    "        - graph: 图的邻接表表示.\n",
    "        - isDirected: 图是否有向.\n",
    "\n",
    "    Returns:\n",
    "        - groups: 环分组,每个环的大小>=2.\n",
    "        - inCycle: 每个点是否在环中.\n",
    "        - belong: 每个点所在的环的编号.如果不在环中,则为-1.\n",
    "        - depth: 每个点在拓扑排序中的最大深度,最外层的点深度为0.\n",
    "    \"\"\"\n",
    "\n",
    "    def max(a: int, b: int) -> int:\n",
    "        return a if a > b else b\n",
    "\n",
    "    depth = [0] * n\n",
    "    startDeg = 0 if isDirected else 1\n",
    "    deg = [0] * n\n",
    "    if isDirected:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                deg[v] += 1\n",
    "    else:\n",
    "        for u in range(n):\n",
    "            deg[u] = len(graph[u])\n",
    "\n",
    "    queue = deque([i for i in range(n) if deg[i] == startDeg])\n",
    "    visited = [False] * n\n",
    "    while queue:\n",
    "        cur = queue.popleft()\n",
    "        visited[cur] = True\n",
    "        for next_ in graph[cur]:\n",
    "            depth[next_] = max(depth[next_], depth[cur] + 1)\n",
    "            deg[next_] -= 1\n",
    "            if deg[next_] == startDeg:\n",
    "                queue.append(next_)\n",
    "\n",
    "    def dfs(cur: int, path: List[int]) -> None:\n",
    "        if visited[cur]:\n",
    "            return\n",
    "        visited[cur] = True\n",
    "        path.append(cur)\n",
    "        for next in graph[cur]:\n",
    "            dfs(next, path)\n",
    "\n",
    "    groups = []\n",
    "    for i in range(n):\n",
    "        if visited[i]:\n",
    "            continue\n",
    "        path = []\n",
    "        dfs(i, path)\n",
    "        groups.append(path)\n",
    "\n",
    "    inCycle, belong = [False] * n, [-1] * n\n",
    "    for gid, group in enumerate(groups):\n",
    "        for node in group:\n",
    "            inCycle[node] = True\n",
    "            belong[node] = gid\n",
    "\n",
    "    return groups, inCycle, belong, depth\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    #  100075. 有向图访问计数\n",
    "    # https://leetcode.cn/problems/count-visited-nodes-in-a-directed-graph/\n",
    "    # 给定一个有向基环树，求每个结点可以到达的结点数。\n",
    "    class Solution:\n",
    "        def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "            n = len(edges)\n",
    "            adjList = [[] for _ in range(n)]\n",
    "            for u, v in enumerate(edges):\n",
    "                adjList[u].append(v)\n",
    "\n",
    "            groups, inCylce, belong, _ = cyclePartition(n, adjList, isDirected=True)\n",
    "\n",
    "            @lru_cache(None)\n",
    "            def dfs(cur: int) -> int:\n",
    "                if inCylce[cur]:\n",
    "                    return len(groups[belong[cur]])\n",
    "                return 1 + dfs(edges[cur])\n",
    "\n",
    "            return [dfs(i) for i in range(len(edges))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import Counter\n",
    "from itertools import permutations\n",
    "from math import inf\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        dfn, stk, low, instk = [0 for _ in range(n)], [0 for _ in range(n + 2)], [0 for _ in range(n)], [False for _ in\n",
    "                                                                                                         range(n)]\n",
    "        id, size = [0 for _ in range(n)], [0 for _ in range(n)]\n",
    "        scc_cnt, top, timestamp = 0, 0, 1\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            g[i].append(edges[i])\n",
    "\n",
    "        def tarjan(u: int) -> None:\n",
    "            nonlocal timestamp\n",
    "            nonlocal top\n",
    "            nonlocal scc_cnt\n",
    "            dfn[u] = low[u] = timestamp\n",
    "            timestamp += 1\n",
    "            stk[(top + 1)] = u\n",
    "            top += 1\n",
    "            instk[u] = True\n",
    "\n",
    "            for i in range(len(g[u])):\n",
    "                j = g[u][i]\n",
    "                if dfn[j] == 0:\n",
    "                    tarjan(j)\n",
    "                    low[u] = min(low[u], low[j])\n",
    "                elif instk[j]:\n",
    "                    low[u] = min(low[u], dfn[j])\n",
    "\n",
    "            if dfn[u] == low[u]:\n",
    "                scc_cnt += 1\n",
    "                while stk[top] != u:\n",
    "                    d = stk[top]\n",
    "                    instk[d] = False\n",
    "                    top -= 1\n",
    "                    id[d] = scc_cnt\n",
    "                    size[scc_cnt] += 1\n",
    "                # 多做一次,将u也排出来\n",
    "                d = stk[top]\n",
    "                instk[d] = False\n",
    "                top -= 1\n",
    "                id[d] = scc_cnt\n",
    "                size[scc_cnt] += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            if dfn[i] == 0:\n",
    "                tarjan(i)\n",
    "        res = [0 for _ in range(n)]\n",
    "\n",
    "        e = [[] for _ in range(n)]\n",
    "        din = [0 for _ in range(n)]\n",
    "        st = [False for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if id[i] != id[edges[i]]:\n",
    "                e[id[i]].append(id[edges[i]])\n",
    "                din[id[edges[i]]] += 1\n",
    "\n",
    "        def dfs(u: int) -> int:\n",
    "            for i in range(len(e[u])):\n",
    "                j = e[u][i]\n",
    "                if st[j] == True:\n",
    "                    size[u] += size[j]\n",
    "                    continue\n",
    "                st[j] = True\n",
    "                size[u] = size[u] + dfs(j)\n",
    "            return size[u]\n",
    "\n",
    "        for i in range(1, scc_cnt + 1):\n",
    "            if din[i] == 0:\n",
    "                dfs(i)\n",
    "        for i in range(n):\n",
    "            res[i] = size[id[i]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVisitedNodes(self, edges: List[int]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        vis = [0 for _ in range(n)]\n",
    "        instack = [0 for _ in range(n)]\n",
    "        low = [0 for _ in range(n)]\n",
    "        dfn = [0 for _ in range(n)]\n",
    "        graph = [[] for _ in range(n)]\n",
    "        color = [i for i in range(n)]\n",
    "        for idx, edge in enumerate(edges):\n",
    "            graph[idx].append(edge)\n",
    "        global cnt\n",
    "        stack = []\n",
    "        global stackflag\n",
    "        cnt = 0\n",
    "        stackflag = 0\n",
    "        def tarjan(now):\n",
    "            global cnt\n",
    "            global stackflag\n",
    "            # 初始化low dfn\n",
    "            cnt += 1\n",
    "            low[now] = cnt\n",
    "            dfn[now] = cnt\n",
    "            # 节点入栈\n",
    "            stack.append(now)\n",
    "            stackflag += 1\n",
    "            instack[now] = 1\n",
    "            for nxt in graph[now]:\n",
    "                if dfn[nxt] == 0:\n",
    "                    tarjan(nxt)\n",
    "                    low[now] = min(low[now], low[nxt])\n",
    "                elif instack[nxt]:\n",
    "                    low[now] = min(low[now], low[nxt])\n",
    "            if low[now] == dfn[now]:\n",
    "                while stack[stackflag-1] != now:\n",
    "                    top = stack[stackflag-1]\n",
    "                    color[top] = color[now]\n",
    "                    stack.pop()\n",
    "                    stackflag -= 1\n",
    "                    instack[top] = 0\n",
    "                stack.pop()\n",
    "                stackflag -= 1\n",
    "                instack[now] = 0\n",
    "                \n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            stack = []\n",
    "            stackflag = 0\n",
    "            if dfn[i] == 0:\n",
    "                tarjan(i)\n",
    "        newgraph = [[] for _ in range(n)]\n",
    "        newval = [0 for _ in range(n)]\n",
    "        for idx, edge in enumerate(edges):\n",
    "            newval[color[idx]] += 1\n",
    "            newstart = color[idx]\n",
    "            newend = color[edge]\n",
    "            if newstart != newend and newend not in newgraph[newstart]:\n",
    "                newgraph[newstart].append(newend)\n",
    "        def dfs(now):\n",
    "            sonnum = len(newgraph[now])\n",
    "            if sonnum == 0:\n",
    "                colorans[now] = newval[now]\n",
    "            elif colorans[now] > -1:\n",
    "                return colorans[now]\n",
    "            else:\n",
    "                colorans[now] = newval[now]\n",
    "                for item in newgraph[now]:\n",
    "                    colorans[now] += dfs(item)\n",
    "            return colorans[now]\n",
    "        ans = []\n",
    "        colorans = [-1 for i in range(n)]\n",
    "        for idx in range(n):\n",
    "            colorans[color[idx]] = dfs(color[idx])\n",
    "            ans.append(colorans[color[idx]])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
